Двойственная задача

Сформулировать задачу, двойственную линейной производственной задаче, как задачу определения расчетных оценок ресурсов, и найти ее решение, пользуясь второй основной теоремой двойственности (о дополняющей нежесткости). Указать оценку единицы каждого ресурса, минимальную суммарную оценку всех ресурсов, оценки технологий.

Применить найденные двойственные оценки ресурсов к решению следующей задачи.

Сформулировать задачу о "расшивке узких мест производства" и составить математическую модель. Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о расшивке узких мест производства при условии, что дополнительно можно получить от поставщиков не более одной трети первоначально выделенного объема ресурса любого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительную возможную прибыль.

По пунктам 1, 2, 3 составить сводку результатов [10, c. 21].

Знакомый предприниматель П (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у₁рублей за каждую единицу первого ресурса, у₂руб – второго, у₃руб – третьего. Возникает вопрос: при каких ценах у₁, у₂, у₃мы можем согласиться с предложением П.

Величины у₁, у₂, у₃принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.

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

1. z=27x1+39x2+18x3+20х4max

(2) 2x1 + 1x2 + 6x3 + 5x4140

3x2 + 4x490

3x1 + 2x2 + 4x3198

(3) x10,x20,x30,x40

Тогда двойственной задачей к (1-3) будет следующая :

(1)’ f = 140y1 + 90y2 + 198y3  min

2y1 + 3y3  27

(2)’ y1 + 3y2 + 2y3  39

6 y1 + 4y3  18

5у1 + 4у2 20

(3)’ у10, у20, у30

Следует найти вектор двойственных оценок у(у₁,y₂,y₃)

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений (х₁, х₂, х₃, х₄) и(y₁, y₂, y₃) пары двойственных задач необходимо и достаточно выполнение условий

х1 (2y1 + 3y3 - 27) = 0

х2 ( y1 + 3y2 + 2y3 - 39) = 0

х3 (6 y1 + 4y3 - 18) = 0

х4 (5у1 + 4у2 - 20) = 0

y1 (2x1 + 1x2 + 6x3 + 5x4 - 140) = 0

y2 ( 3x2 + 4x4 - 90) = 0

y3 (3x1 + 2x2 + 4x3 - 198) = 0

Ранее было найдено, что в решении исходной задачи x10,x20, поэтому

2y1 + 3y3 - 27 = 0

y1 + 3y2 + 2y3 - 39 = 0

Если же учесть, что первый ресурс был избыточным (х5=18) и, согласно той же теореме двойственности, ее двойственная оценка равна нулю

у1=0,

то приходим к системе уравнений

3y3 - 27 = 0

3y2 + 2y3 - 39 = 0

3y3 - 27 = 0 | :3

y3 – 9=0

y3 = 9

3y2 + 2y3 - 39 = 0

3y2 + 2*9 - 39 = 0

3у2=21

у2=7

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

у₁=0; у₂=7; у₃=9, (4)

причем общая оценка всех ресурсов равна 2412.

Задача о "расшивке узких мест производства"

При выполнении оптимальной производственной программы второй и третий ресурсы используются полностью, т.е. образуют узкие места производства. Будем их заказывать дополнительно. Пусть T(t₁,t₂,t₃)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие

H + Q^-1T 0.

Задача состоит в том, чтобы найти вектор

T (t₁, 0, t₃),

максимизирующий суммарный прирост прибыли

W = 7t₂ + 9t₃ (1)

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

18 1 1/9 -2/3 0 0

30 + 0 1/3 0 t2 ≥ 0 (2)

46 0 -2/9 1/3 t3 0

предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида

0 140

t2 ≤ 1/3 90 (3)

t3 198

причем по смыслу задачи

t₁0, t₃ 0. (4)

Переписав неравенства (2) и (3) в виде:

1/9t2 - 2/3t3 ≥ -18

1/3t2 ≥ -30 *-1

-2/9t2 + 1/3t3 ≥ -46

-1/9t2 + 2/3t3 ≤ 18

-1/3t2 ≤ 30 (5)

2/9t2 - 1/3t3 ≤ 46

t2≤90/3 ; t3≤198/3 - t2 ≤ 30, t3 ≤ 66 (6)

t3

66

М

27

0 30 t2

1) t2=0; t3=27

t3=0; t2=-162

3) t2=0; t3=-138

t3=0’ t2=207

Точка М на пересечении

t2 ≤ 30

-1/9t2 + 2/3t3 ≤ 18

t2=30; t3=32.

Точка Mимеет координаты (30;32)

W = 7t2 + 9t3  max

W= 7*30 + 9*32=210+288=498

W= 498

Сводная таблица результатoв

Cj	27	39	18	20	Bi	X4+i	Yi	Ti
	2	1	6	5	140	18	0	0
aij	0	3	0	4	90	0	7	30
	3	2	4	0	198	0	9	32
Xj	46	30	0	0	2412			498
j	0	0	18	8

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

Однородный продукт, сосредоточенный вm пунктах производства (хранения) в количествах a1,a2,…..a_m единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b1,b2,….b_n единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна c_ij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Исходные данные имеют вид: 2 1 6 5

А(а₁, а₂, а₃) = (70; 40; 60); В(b₁, b₂, b₃, b₄) = (37; 39; 48; 40); С = 5 3 7 6

3 2 4 2

A - вектор объемов производства

B - вектор потребностей потребителей

C - матрица транспортных издержек

Обозначим через x_ij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю.

--открытая модель транспортной задачи

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

найти план перевозок

Х=(x_ij), i= 1,m; j = 1,n

минимизирующий общую стоимость всех перевозок

L=c_ij*x_ij

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

Xija_i , i= 1,m

Общий объем производства а_i =71+40+60=171

b_i = 38+39+48+40=165 больше, требуется всем потребителям , т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 171-165=6 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение легко построить по правилу северо-западного угла.

Важные формулы:

p_i=c_ij-q_i

q_i= c_ij - p_i

_ij = p_i + q_j - c_ij

	37	39	48	40	6	pi
70	^2 37	^1 33	^6	^5	^0	0
40	^5	^36	^7 34 -	^6	^0^+	2
60	^3	^2	^4 14 +	^2 40	^0 6 -	-1
qi	2	1	5	3	1

p_i=0, q_i=2-0=2, q_i=1-0=1

q_i=1, p_i=3-1=2

p_i=2, q_i=7-2=5

q_i=5, p_i=4-5=-1

p_i=-1, q_i=2—1=3

p_i=-1, q_i=0—1=1

Полученные результаты можно проверить. p_i+q_i=индекс. Например, 2+0=2; 3+-1=2.

Теперь понадобится формула _ij = p_i + q_j - c_ij

₁₃=0+5-6= -1

₁₄=0+3-5= -2

₁₅=0+1-0= 1

₂₁=2+2-5= -1

₂₄=2+3-6= -1

₂₅=2+1-0= 3

₃₁=-1+2-3= -2

₃₂=1+-1-2= -2

Унас есть положительные числа - ₁₅ , ₂₅ - самое большое положительное число.

₂₅ - это число 6.

Производим операцию заново.

	37	39	48	40	6	pi
70	^2 37	^1 33	^6	^5	^0	0
40	^5	^36	^7 28	^6	^06	2
60	^3	^2	^4 20	^2 40	^0	-1
qi	2	1	5	3	-2

_ij = p_i + q_j - c_ij

₁₃=-1

₁₄=-2

₁₅=-2

₂₁=-1

₂₄=-1

₃₁=-2

₃₂= -2

₃₅=-3

В данной таблице все ∆ij 0, i = 1,m; j = 1,n .

Данное базисное решение будет оптимальным

37 33 0 0

Х = 0 6 28 0

0. 0 20 40

L=c_ij*x_ij = 37*2+33*1+6*3+28*7+20*4+40*2 =

74+33+18+196+80+80 = 481(Zоптимальное)

Zопорное = 37*2+33*1+6*3+34*7+14*4+40*2=74+33+18+238+56+80=499

∆Z = Zопорн. – Zоптимальное=499-481=18