Применение метода двойного предпочтения и метода потенциалов для решения транспортной задачи в линейном программировании

Введение

В 1930 г. впервые прозвучала постановка задачи линейного программирования в работах советского экономиста А.Н. Толстого, имеющая вид предложения по составлению такого плана перевозки груза между пунктами, чтобы общий пробег транспорта был наименьшим; основы математического аппарата для решения экономических задач линейного программирования были созданы в 1939 г. академиком Л.В. Канторовичем и его учениками.

В настоящее время транспортная задача линейного программирования широко применяется как в теоретических разработках, так и в практике планирования различных экономических процессов. Особо важное значение она имеет при решении вопросов рационализации поставок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.

Также транспортная задача применяется при решении экономических задач, которые по своему характеру не имеют ничего общего с транспортировкой груза. К задачам такого типа относят:

·        Увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега;

·        Оптимальное закрепление за станками операций по обработке деталей;

·        Оптимальное назначения, или проблема выбора;

·        Задачи размещения с учетом транспортных и производственных затрат.

Как и для других задач линейного программирования, итерационный процесс по отыскании. Оптимального плана транспортной задачи начинают с нахождения опорного плана, найти который можно с помощью следующих методов:

·        Метод северо-западного угла;

·        Метод минимальной стоимости;

·        Метод двойного предпочтения;

А оптимальный план находится с помощью следующих методов:

·        Метод потенциалов;

·        Дельта-метод решения транспортной задачи;

В данной курсовой работе используется для нахождения опорного плана используется метод двойного предпочтения. Для определения оптимального плана - метод потенциалов.

оптимальный план минимизация перевозка

1. ПОСТАНОВКА ЗАДАЧИ

Нефтеперерабатывающий завод получает 4 вида полуфабрикатов: 200 тыс. литров алкилата, 350 тыс. литров бензина прямой перегонки, 250 тыс. литров крекинг бензина, 100 тыс. литров изопентана.

В результате смешивания этих 4-ех компонентов в разных пропорциях образуется 3 сорта авиационного бензина:

Бензин А-2:3:5:2

Бензин В-3:1:2:1

Бензин С-2:2:1:3

Стоимость 1 тыс. литров указанных сортов бензина характеризуется числами: А-120 руб. В-100руб, С-150руб.

Таблица 1

Виды полуфабрикатов	Пропорциональное содержание полуфабрикатов			Ограничения полуфабрикатов в бензине, тыс.л.
Марка бензина	А	В	С
Алкилат	2	3	2	100
Крединг-бензин	3	1	2	125
Бензин прямой перегонки	5	2	1	150
Изопентон	2	1	3	50
Стоимость 1 тыс.л. Бензина (руб.)	120	100	150

Определить план смешивания компонентов, при котором будет достигнута максимальная стоимость всей продукции.

Задачу решить симплексным методом, используя язык программирования Turbo C и реализовать на ПЭВМ IBM PC 486

2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

Математическая модель в общем виде:

при ограничениях

  

Вводятся обозначения для искомой задачи:

m - вид полуфабрикатов,

n - сорта бензина,

a_i - пропорциональное содержание полуфабрикатов в бензине,

b_j - ограничения полуфабрикатов в бензине, тыс.л.

С_ij - стоимость бензина,

x_ij - объем выпуска бензина,

Z - минимальная стоимость всей продукции.

Математическая модель данной ЗЛП:

 

при ограничениях:

3. МЕТОД РЕАЛИЗАЦИИ МОДЕЛИ

Поставлена задача линейного программирования. Найти  максимальное значение функции

Z=C1X1+C2X2+...+CnXn

при ограничениях

a11x1+a12x2+...+a1nxn=b1

a21x1+a22x2+...+a2nxn=b2

............................................x1+am2x2+amnxn=bm≥0(j=1,2,...n)

bi≥0(i=1,2,...m)

Предполагается, что система ограничений задачи содержит m единичных векторов, причем без ограничения общности можно положить, что единичными являются первые m векторов.

Z=C1X1+C2X2+...+CnXn

при ограничениях

x1+a1,m+1 xm+1+...+a1nxn=b1+a2,m+1 xm+1+...+a2nxn=b2

.....................................................+am,m+1+xm+1+...+amnxn=bm≥0(j=1,2,...n)

Алгоритм симплексного метода представляет собой способ целенаправленного перебора планов, чтобы значения линейной формы в задачах на минимум уменьшалось при переходе от одного опорного плана к другому, число шагов для достижения этой цели m≤k≤2m, где m-число уравнений или размеренность базиса.

Заполняется исходная таблица. После чего производится вычисления в последовательности:

Подсчитывается Zj-Cj и определяется, не является ли рассматриваемый план оптимальным, т.е. не выполняется ли для всех xj условие: Zj-Cj≤0

Если для некоторого значение Zj -Cj>0, то выбирается вектор, который может быть введен в базис. Для этого разыскивается какое-нибудь, для которого max(Zj-Cj)=Zk-Ck>0, тогда Pk вводится в базис.

Выбирается вектор, который подлежит исключению из базиса. Это вектор для которого: для всех xik>0, тогда Pi -исключается из базиса.

Если все, то линейная форма неограниченна снизу.

После выделения направляющей строки и направляющего столбца, таблица преобразуется по формуле полного исключения.

В результате каждой итерации образуется новый опорный план. В конце концов, либо придем к оптимальному плану, либо убедимся в неограниченности линейной формы задачи.

Вычисления сводятся в табл.2

Таблица №2

i	Б	СБ	Ро	С1	С2	…	С1	…	Сm	Cm+1	...	Cj	...	Ck	...	Cn
				P1	P1	...	P1	...	Pm	Pm+1	...	Pj	...	Pk	...	Pn
1	P1	С1	X1	1	0	...	0	...	0	X1	...		...		...	X1n
2	P2	С2	X2	0	1	...	0	...	0		...		...		...	X2n
...	...	...	...	...	...	...	...	...	...	...	...		...		...	...
1	P1	С1	X1	0	0	...	1	...	0		...		...		...	X1n
...	...	...	...	…	...	...		...	...	...	...		...		...
m	Pm	Сm	Xm	0	0	...	0	...	1		...		...		...	Xmn
m+1			Z0	0	0	...	0	...	0		...		...		...

. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

.1 Вводятся А,В,С

.2 Заполняется симплексная таблица

.3 Вычисляется базис

.4 Находится опорный план и Z0

.5 Проверяется условие в (m+1)- строки Zj-Cj<=0 на min

.6 Если условие выполняется, то выполняется переход на пункт 4.10

.7 Выбирается вектор Pk по max(Zj-Cj)=Zk-Ck>0

.8 Выбирается вектор Pl, подлежащий исключению из базиса для которого: для всех xik>0

.9 Таблица преобразуется продолжением полного исключения и переход на пункт 4.4

.10 Печать Xopt и Zopt

. ВЫЧИСЛИТЕЛЬНАЯ СХЕМА

Находится первоначальный опорный план методом двойного предпочтения.

Таблица 4

10 0	16 0	3 14	8 0	15 0	14
3 0	14 0	12 0	9 0	1 25	25
2 40	20 16	4 0	11 0	5 0	56
7 0	17 24	13 6	8 10	15 5	45
40	40	20	10	30	140

.

Решение данной задачи осуществляется методом потенциалов.

Таблица 5

Шаг 1
Строки	Ui	Столбцы					ai
		1	2	3	4	5
		Vj
		3	7	-2	5	-11
1	0	10 0	16 0	3 14	8 0	15 0	14
2	10	3 0	14 0	12 0	9 0	1 25	25
3	13	2 40	20 11	4 0	11 0	5 5	56
4	-4	7 0	17 29	13 6	8 10	15 0	45
bj		40	40	20	10	30	140

.

Таблица 6

Шаг 2
Строки	Ui	Столбцы					ai
		1	2	3	4	5
		Vj
		-11	7	3	-2	-8
1	0	10 0	16 0	8 0	15 0	14
2	9	3 0	14 0	12 0	9 0	1 25	25
3	13	2 40	20 5	4 6	11 0	5 5	56
4	10	7 0	17 35	13 0	8 10	15 0	45
bj		40	40	20	10	30	140

.

Таблица 7

Шаг 3
Строки	Ui	Столбцы					ai
		1	2	3	4	5
		Vj
		1	19	3	10	4
1	0	10 0	16 5	3 9	8 0	15 0	14
2	-3	3 0	14 0	12 0	9 0	1 25	25
3	1	2 40	20 0	4 11	11 0	5 5	56
4	-2	7 0	17 35	13 0	8 10	15 0	45
bj		40	40	20	10	30	140

Так как  , то получается оптимальный план на третьем шаге.

.

6. БЛОК-СХЕМА

7. ПРОГРАММА

Данная задача линейного программирования реализована посредством MS Excel. Для этого используется процедура Excel «Поиск решения»,

где:

·        Установить целевую ячейку - служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу:

o   Равной - служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного значения числа). Чтобы установить число, необходимо ввести его в поле;

o   Изменяя ячейки - служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку;

o   Предположить - используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки;

o   Ограничение - служит для отображения списка граничных условий поставленной задачи;

o   Добавить - используется для отображения диалогового окна Добавить ограничение;

o   Изменить - применяется для отображения диалогового окна Изменить ограничение;

o   Удалить - служит для снятия указанного ограничения;

o   Выполнить - используется для запуска поиска решения поставленной задачи;

o   Закрыть - служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить;

o   Параметры - применяется для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения;

o   Восстановить - служит для очистки полей окна диалога и восстановления значений параметров по умолчанию.

8. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

8.1     Включить ЭВМ.

.2       Запустить прикладную программу MS Excel.

.3       Открыть новый рабочий лист (Вставка/Лист).

.4       В ячейки диапазона А1:Е4 разместить таблицу стоимости перевозок.

.5       В ячейки диапазона А10:Е10 ввести следующие формулы:

А10 = СУММ(А6:А9)

В10 = СУММ(В6:В9)

С10 = СУММ(С6:С9)

D10 = СУММ(D6:D9)

Е10 = СУММ(Е6:Е9)

.6       В ячейки диапазона F6:F10 ввести следующие формулы:

F6 = СУММ(А6: E6)

F7 = СУММ(А7: E7)

F8 = СУММ(А8: E8)

F9 = СУММ(А9: E9)

.7       В ячейки диапазона G6:G9 ввести значения соответствующие запасам на складах.

.8       В ячейки диапазона А11:Е11 ввести значения соответствующие потребностям на птредприятиях.

.9       В ячейку F10 ввести формулу целевой функции = СУММПРОИЗВ(A1:E4;A6:E9).

.10     Выбрать на панели инструментов Данные/Анализ/Поиск решения.

.11     Установить целевую ячейку содержащую оптимизируемое значение (F10).

.12     Установить переключатель Равной минимальному значению, т.к. в поставленной задаче требуется вычислить минимальный объем затрат.

.13     В поле Изменяя ячейки задать диапазон подбираемых параметров ($A$6:$E$9).

.14     Определить набор ограничений. Для этого щелкнуть на кнопке Добавить и ввести следующие ограничения $A$10:$E$10 = $A$11:$E$11, $A$6:$E$9 = целое, $A$6:$E$9 >= 0, $F$6:$F$9 = $G$6:$G$9.

.15     Щелкнуть на кнопке Выполнить.

.16     В диалоговом окне Результаты поиска решения установить переключатель в положение Сохранить найденное решение.

.17     Полученные результаты вывести на печать.

9. РЕЗУЛЬТАТ СЧЕТА ПО ПРОГРАММЕ

Результат вычислений:

Оптимальный план:

Xопт =	0 0 40 0	5 0 0 35	9 0 11 0	0 0 0 10	0 25 5 0	14 25 56 45
	40	40	20	10	30

Целевая функция: Z_опт = 956.

. ЭКОНОМИЧЕСКОЕ ОБЪЯСНЕНИЕ РЕЗУЛЬТАТОВ

В результате решения транспортной задачи по минимизации затрат на перевозку товаров с четырех складов на пять предприятий был получен оптимальный план:

Xопт =	0 0 40 0	5 0 0 35	9 0 11 0	0 0 0 10	0 25 5 0	14 25 56 45
	40	40	20	10	30

Чтобы затраты на перевозку товара с четырех складов на пять предприятий были минимальны, необходимо таким образом спланировать перевозки:

На первое предприятие 40 т товара с четвертого склада.

На второе предприятие 5 т товара с первого склада и 35 т с четвертого склада.

На третье предприятие 9 т товара с первого склада и 11 т с третьего склада.

На четвертое предприятие 10 т товара с четвертого склада.

На пятое предприятие 25 т товара со второго склада и 5 т с третьего склада.

При таком плане стоимость перевозок составляет 956 рублей.

В результате оптимизации плана получена экономия Z_о - Z_опт =

= 1108 - 56 = 152 рубля.

ЗАКЛЮЧЕНИЕ

В результате выполнения курсовой работы закрепила знания по математическим и программным средствам моделирования при решении конкретной производственной программы.

При выполнении курсовой работы закрепила навыки нахождения оптимального плана транспортной задачи с помощью метода потенциалов.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

·   Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко «Математическое программирование» М. «Высшая школа», 1980г.

·   С.А. Соколицин «Применение математических методов в экономике и организации машиностроительного производства» Л, «Машиностроение», 1970г.

·   ЕСПД Схема алгоритмов и программ ГОСТ 19.002 - 80, ГОСТ 19.003-80, издательства стандартов, 1980г.

·   Методические указания к курсовой работе по дисциплине «Математические методы», Таганрог, ТАК, 2010г.