Iv. формулировка двойственной линейной задачи и её решение двойственным симплексным методом.

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

(1) z=30x₁+25x₂+14x₃+12х₄®max

	{

(2) 2x₁ + 1x₂ + 6x₃ + 5x₄ £ 140

3x₂ + 4x₄ £ 90

3x₁ + 2x₂ + 4x₃ £ 198

(3) x_i ³ 0, i=1...4.

{

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

(1)’ f = 140y₁ + 90y₂ + 198y₃ ® min

2y₁ + 4y₃ ³ 30

(2)’ y₁ + 3y₂ + 2y₃ ³ 25

5y₂ + 4y₃ ³ 14

5у₁ + 4у₂ ³ 12

(3)’ y_i ³ 0, i = 1...3.

Двойственная задача (1)’- (3)’ получается из исходной (1)-(3) следующим образом:

1) каждому неравенству-ограничению исходной задачи ставим в соответствие переменную двойственной задачи (у), принимающую неотрицательные значения;

2) транспонируем матрицу коэффициентов при неизвестных;

3) правые части ограничений заменяем коэффициентами целевой функции;

4) меняем направление неравенств;

5) коэффициенты целевой функции заменяем правыми частями ограничений;

6) то максимизации целевой функции переходим к минимизации.

Требуется найти оценку единицы каждого вида ресурса У=(у₁,у₂,у₃) (вектор двойственных оценок минимизирующий общую стоимость всех ресурсов, выраженную через функцию f(y₁,y₂,y₃), при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации этой продукции (ограничение 2’), причём оценки ресурсов не могут быть отрицательными (ограничение 3’).

Согласно первой теоремы двойственности, которая гласит, что одна из пары двойственных задач имеет оптимальное решение, то имеет решение и вторая задача, причём экстремальные значения целевых функций равны.

Для решения задачи двойственным симплексным методом введём дополнительные переменные и перепишем (1)’-(3)’ следующим образом :

{

(1)’’ f= 140y₁ + 90y₂ + 198₃ ® min

-2y₁ - 3y₃ + y₄ = -27

(2)’’ - y₁ - 3y₂ - 2y₃ + y₅ = -39

-6y₁ - 4y₃ + y₆ = -18

-5у₁ - 4y₂ + y₇ = -20

(3)’’ y_i ³ 0, i = 1...7.

Для решения задачи (1)”-(2)” надо построить симплексную таблицу, что и сделано далее.

Симплексная таблица в общем виде.

№	Уб	Вб	Н	в1	в2	в3	в4	в5	в6	в7
				У1	У2	У3	У4	У5	У6	У7
	У1	В1	-С1					-а51	-а61	-а71
	У2	В2	-С2					-а52	-а62	-а72
	У3	В3	-С3					-а53	-а63	-а73
	У4	В4	-С4					-а54	-а64	-а74
	–	–	SСiвj					D5	D6	D7

Подставив соответствующие значения, имеем :

	Уб	Вб	Н
				У1	У2	У3	У4	У5	У6	У7
	У4		-27	-2		-3
	У5		-39	-1	-3*	-2
	У6		-18	-6		-4
	У7		-20	-5	-4
	–	–		-140	-90	-198
	У4		-27	-2		-3
	У2			1/3		2/3		-1/3
	У6		-18	-6		-4
	У7			-11/3		8/3		-4/3
	–	–		-110		-138		-30
	У3			2/3			-1/3
	У2			-1/9			2/9	-1/3
	У6			-10/3			-4/3
	У7			-49/9			8/9	-4/3
	–	–		-18			-46	-30

Алгоритм решения задачи.

1. Просматриваем значения 4-го столбца (Н). Если все С_j>0, то оптимальное решение найдено .

2. Если какие-либо -C_j < 0, то находим min(-C_j<0 ) = -С_к .

3. У_к исключаем из базисных переменных .

4. Отыскиваем переменную включаемую в базис:

а. Находим min(D_i/a_ij)=D_m/a_ij (для всех a_ij < 0), где j - номер строки , соответствующей -С_к.

б. У_m включаем в число базисных переменных.

5. Преобразуем исходную, строим новую симплексную таблицу.

6. Возвращаемся в пункт 1.

Опорный план первой двойственной симплексной таблицы.

При данном производстве ни один из ресурсов не продаётся и прибыли от продажи ресурсов равны 0. Так как ресурсы не продаются, то числа –27,-39,-18,-20 соответствуют прибыли, полученной от продажи единицы первого, второго, третьего, четвёртого товара в случае его производства или суммарным затратам всех видов ресурсов на производство i-ого продукта, соответственно. Они показывают на сколько единиц возможно увеличить прибыль от продажи всех видов ресурсов, предназначенной для изготовления одной единицы i-ого товара, то есть суммарные затраты. Значения –140,-90,-198 в строке оценочных коэффициентов показывают, что все ресурсы остались в том же количестве, что и были, то есть не были использованы.

Вся эта таблица – для оптимальной продажи ресурсов. Так как существует возможность увеличения прибыли (это показывает числа столбца базисного решения), то определяем минимальные цены ресурсов по которой выгодно их продать. Наиболее высокой ценой продажи должны обладать ресурсы затрачиваемые на производство второго товара. Эта цена (39 денежных единиц) служит ограничивающим фактором, то есть менее чем по этой цене предприниматель не согласится уступить эти ресурсы. Второй товар изготавливается из трёх ресурсов. Наиболее выгодно будет уступить второй ресурс, так как из него получается меньше всего изделий. В связи с этим в базис помещается оценка второго ресурса, а второй товар исключаем.

Решение двойственной задачи на основе второй основной теоремы двойственности (о дополняющей нежесткости).

Вторая теорема двойственности (о дополняющей нежесткости ) гласит: для того, чтобы х* =(х₁,...,х_n) и y*=(y₁,...,y_n) являлись оптимальным решением соответствующих задач двойственной пары, необходимо и достаточно выполнение условий :

X_j S a_ij y_j – C_j = 0 j = 1,n

Y_i S a_ij x_j – в_i = 0 i = 1,m

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

{

Итак, для решения задачи 1”-3” необходимо и достаточно выполнения условий:

x₁(2y₁ + 3y₃ - 27) = 0

x₂( y₁ + 3y₂ + 2y₃ - 39) = 0

x₃(6y₁ + 4y₃ - 18) = 0

x₄(5y₁ + 4y₂ - 20) = 0

	{

y₁(2x₁ + 1x₂ + 6x₃ + 5x₄ - 140) = 0

y₂( 3x₂ + 4x₄ - 90) = 0
y₃(3x₁ + 2x₂ + 4x₃ - 198) = 0

Ранее было найдено, что в решении исходной задачи х₁>0 и x₂>0. Поэтому 2y₁ + 3y₃ - 27 = 0

y₁ + 3y₂ + 2y₃ - 39 = 0

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

	{

3y₃ = 27

3у₂ + 2y₃ = 39

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

у₁ = 0 у₂ =7 , у₃ = 9,
причём общая оценка всех ресурсов равна:

f_min =140*0 + 90*7 + 198*9 = 2412.

Заметим, что данное решение содержалось в последней строке последней симплексной таблицы исходной задачи.