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

при условии что,

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

Экономический смысл переменных:

Z – целевая функция прямой задачи (суммарные затраты);

Z' – целевая функция двойственной задачи (суммарная потенциальная прибыль от перевозки груза);

С_ij – стоимость перевозки единицы продукции из i-го пункта в j-ый;

X_ij – объем перевозок от i-го поставщика j-му потребителю;

U_i – условная плата перевозчику за вывоз единицы груза из i-го пункта отправления;

V_j – условная плата перевозчику за доставку единицы груза в j-ый пункт назначения.

Потребители Поставщики	В₁	В₂	В₃	В₄	В₅	U_i

А₁		³⁵⁰ 4	8	^{50 -}^W		^+W	U₁=-2
	6	9		0
А₂		9	^{100 +W}				²⁰⁰	^-W 0	U₂=-6
	5		10	4
А₃		7	¹⁵⁰	^-^W	¹⁰⁰	^+W 8	²⁵⁰ 6	0	U₃ =0
11
V_j	V₁=6	V₂=11	V₃=8	V₄=6	V₅= 6	W=50

Проверяем на вырожденность:

R=m+n-1=3+5-1=7

m= 3 – количество поставщиков;

n = 5 – количество потребителей.

Базисных клеток 7, план не вырожден.

Проверяем план на оптимальность, используя метод потенциалов. Для базисных клеток составляем систему уравнений U_i + V_j = С_ij находим значение потенциалов так как переменных на 1 больше, чем уравнений,

то переменной U₃ присваиваем значение 0 и решаем систему уравнений, получаем

Проверяем выполнение неравенства в свободных: клетках U_i + V_j ≤ С_ij

более всего не выполняется условие U_i + V_j ≤ С_ij, сюда ставим «+W», строим контур перераспределения W и находим его значение:

Перераспределяем W=50 по контуру.

Составляем следующий план:

Потребители Поставщики В₁ В₂ В₃ В₄ В₅ U_i

А₁ ³⁵⁰ ^-^W ^{50 +W} U₁=-6

4 8 6 9 0

А₂ 9 ¹⁵^{0 +W} ¹⁵⁰ ^-W 0 U₂=-6

5 10 4

А₃ ^+W ¹⁰⁰ ^-^W ¹⁵⁰ 8 ²⁵⁰ 6 0 U₃ =0

7 11

V_j V₁=10 V₂=11 V₃=8 V₄=6 V₅= 6 W=100

Так как переменных на i больше, чем уравнений, то переменной U₃ присваиваем значение 0 и решаем систему уравнений, получаем

проверяем выполнение неравенства в свободных клетках U_i + V_j ≤ С_ij,

– более всего не выполняется условие U_i + V_j ≤ С_ij, сюда ставим «+W», строим контур перераспределения W и находим его значение: перераспределяем W=100 по контуру.

Составляем следующий план:

Потребители Поставщики В₁ В₂ В₃ В₄ В₅ U_i

А₁ ²⁵⁰ 4 8 6 9 ¹⁵⁰ 0 U₁=-3

А₂ 9 ²⁵⁰ 5 10 4 ⁵⁰ 0 U₂=-3

А₃ ¹⁰⁰ 7 11 ¹⁵⁰ 8 ²⁵⁰ 6 0 U₃ =0

V_j V₁=7 V₂=8 V₃=8 V₄=6 V₅= 3

Для базисных клеток U_i + V_j = C_ij . Составляем для них систему уравнений. Принимаем U₃=0, так как в строке потенциала U₃ наибольшее количество (три) базисных клеток, решаем систему уравнений и находим количественное значение U_i и V_j :

Проверяем выполнение неравенства U_i + V_j ≤ С_ij, в свободных клетках:

Неравенство U_i + V_j ≤ С_ij,в свободных клетках выполняется, построенной план является оптимальным.

Анализ решения.

1.Оптимальный план перевозки продукции:

– от поставщика А₁ перевозится 250 ед. продукции потребителю В₁; 150 ед. продукции остается у поставщика;

– от поставщика А₂ перевозится 250 ед. продукции потребителю В₂; 50 ед продукции остается у поставщика;

– от поставщика А₃ перевозится 100 ед.продукции потребителю В₁, 150 ед, потребителю В₃, 250 ед. потребителю В₄ .

2.Суммарные затраты на изготовление и перевозку продукции:

ден. ед.