Задачи динамического программирования

 

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

Базисное решение содержит х₁ = 10, х₂ = 0. Максимальное значение функции прибыли равно 40 ден. ед..

Экономический смысл  последней симплекс-таблицы заключается в следующем: Оптимальный план выпуска составляет выпуск 10 изделий х₁. Изделие х₂ целесообразнее не выпускать. При этом сырье первого вида используется полностью, остатки сырья второго и третьего вида  - по 30 единиц каждого. Увеличение запасов сырья второго и третьего вида не повлияет на значение целевой функции, лишь увеличит остаток каждого вида сырья, увеличение запасов сырья первого вида на 1 увеличит значение целевой функции на 1/8.

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

= 80y1 + 60y2 + 40y3 → min;
8y1 + 3y2 + у3≥ 4,  2y1 + 3y2 + 4y3 ≥ 1,
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0

Оптимальное решение  этой задачи имеет вид: = 1/2, = 0, = 0,

= 40 = min.

Двойственные оценки отражают сравнительную  дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство. Дефицитным является ресурс первого типа, ресурсы второго и третьего типов дефицитными не являются.

Задание 2

Постановка  задачи

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

Мощности поставщиков: (30 40 20)

Спрос потребителей: (40 40 30)

Матрица норм затрат А =

Решение

Сформулируем ЗЛП:

= 5x11 + 5x12 + 4x13 + 6x21 + 4x22 + 6x23 + 4x31 + 4x32 + 3x33 → min;

Распределительный метод  является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и  симплексного) содержит такие же три существенных момента.

Прежде всего отыскивается какое-то решение задачи — исходный опорный план. Затем посредством  специальных показателей опорный  план проверяется на оптимальность. Если план оказывается не оптимальным, переходят к другому плану. При  этом второй и последующие планы должны быть лучше предыдущего. Так за несколько последовательных переходов от не оптимального плана приходят к оптимальному.

 

 

	1	2	3	Запасы
1	5	5	4	30
2	6	4	6	40
3	4	4	3	20
Потребности	40	40	30

Проверим необходимое  и достаточное условие разрешимости задачи.  
 ∑a  = 30 + 40 + 20 = 90

∑b = 40 + 40 + 20 = 110

Условие баланса не соблюдается. Запасы не равны потребностям. Следовательно, модель транспортной задачи является открытой. Для приведения задачи к закрытому виду введем фиктивного поставщика №4 с мощностью, равной 20. Все издержки по доставке продукции от данного поставщика любому потребителю принимаем равными нулю.

Маршруты доставки продукции  от фиктивного поставщика A₄ к потребителям мы будем рассматривать в последнюю очередь. Скорее всего, это позволит получить более рентабельное начальное решение.

Согласно условию задачи составим таблицу. (тарифы c_ij располагаются в нижнем правом углу ячейки)

Поставщик	Потребитель			Запас
	B 1	B 2	B 3
A 1	-     5	-     5	-     4	30
A 2	-     6	40     4	-     6	40
A 3	-     4	-     4	20     3	20
A 4	-     0	-     0	-     0	20
Потребность	40	40	30

 

Начальный опорный план получим с помощью метода минимальной  стоимости. Минимальный элемент матрицы тарифов находится в ячейке A₃B₃ и равен 3, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₃ к потребителю B₃ наиболее рентабельный.

Запасы поставщика A₃ составляют 20 единиц продукции. Потребность потребителя B3₁ составляет 30 единиц продукции.

От поставщика A₃ к потребителю B₃ будем доставлять min = { 20 , 30 } = 20 единиц продукции.

Разместим в ячейку A₃B₃ значение равное 20.

Мы полностью исчерпали мощности потребителя А₃ Вычеркиваем строку 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Элемент, равный 4, встречается  в четырех строках таблицы, Возьмем  в качестве минимального элемент, стоящий  в ячейке A₂B₂. Запасы поставщика A₂ составляют 40 единиц продукции, потребности потребителя B₂ – тоже 40 единиц продукции, таким образом, мы полностью удовлетворим потребность потребителя B₂ и исчерпаем мощность потребителя A_2. Вычеркиваем вторую строку и второй столбец из дальнейшего рассмотрения.

Поставщик	Потребитель			Запас
	B 1	B 2	B 3
A 1	-     5	-     5	10     4	30
A 2	-     6	40     4	-     6	40
A 3	-     4	-     4	20     3	20
A 4	-     0	-     0	-     0	20
Потребность	40	40	30

 

Минимальный элемент  матрицы тарифов находится в  ячейке A₁B₃ и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₁ к потребителю B₃ наиболее рентабельный.

Запасы поставщика A₁ составляют 30 единиц продукции. Потребность потребителя B₃ составляет 30 из которых 20 единиц уже удовлетворена.

От поставщика A₁ к потребителю B₃ будем доставлять min = { 30 , 10 } = 10 единиц продукции.

Разместим в ячейку A₁B₃ значение равное 10

Мы полностью удовлетворили  потребность потребителя B₃. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.

Поставщик	Потребитель			Запас
	B 1	B 2	B 3
A 1	20     5	-     5	10     4	30
A 2	0     6	40     4	-     6	40
A 3	-     4	-     4	20     3	20
A 4	20     0	-     0	-     0	20
Потребность	40	40	30

 

В таблице остался  один потребитель, у которого не удовлетворены потребности.

Разместим в ячейку А₁В₁ значение равное 20 и чтобы полностью удовлетворить потребность потребителя В₁ – в ячейку А₄В₁ – значение 20.

Заполненные ячейки будем  называть базисными, остальные - свободными.

Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=5, n+m=4+3=7 , план является вырожденным. Прежде чем двигаться дальше выберем одну незаполненную клетку и запишем в нее число ноль, осуществим так называемую нуль-загрузку. Выбирать следует такие клетки, которые не образуют циклов с другими заполненными клетками, иначе опорного плана не получится.

Вычислим общие затраты  на перевозку всей продукции.

P_нач = 5·20 + 4·10 + 4·40 + 3·20 + 0·20 + 6·0 = 100 + 40 +160+60 = 360

Для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Обозначив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину  можно получить новое опорное решение Х₂. Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, m), приращение целевой функции Δ_lmравно разности двух сумм:

где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+” ; - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”. В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции. Если разность сумм для свободной клетки ( l, m ) меньше нуля, т.е. Δ _lm< 0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ•Δ_lm, т.е. опорное решение можно улучшить. Если же величины Δ_lm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

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