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

Табл. 4

Bj Ai	П1	П2	П3	П4	П5	Ui
СО-1		3	59 7	2		11	U1 =0
5	0
СО-2		2	3	49 4	43 6	7 0	U2= 0
СО-3		47 6	4	3	5	33 0	U3 =0
Vj	V1 =6	V2 =7	V3 =4	V4 =6	V5 = 0

Проверяем план на оптимальность методом максимального

элемента, как в п.З.

Задаем U₂ = 0 и определяем значения потенциалов.

Вычисляем оценки для всех незаполненных клеток (D_ij)

план табл. 4 оптимален.

Определяем значение целевой функции прямойидвойственной задачи:

Исходя из первой теоремы двойственности в условии нашей задачи Z_max=Z_min=1149 (Z=Z’) последний план оптимален

Ответ:

1.Чтобы зарабочий день было убрано максимально возможное количество картофеля, следует распределить студентов по полям следующим образом:

– Из СО-1 выделить 59 человек для уборки картофеля на втором поле П₂, а 11 человек останутся в СО;

– из СО-2 выделить 49 человек для уборки картофеля на П_З и 43 человека для уборки картофеля на П₄, а 7 человек останутся в СО;

– из СО-3 выделить 47 человек для уборки картофеля на П₁, а 33 человека оставить в СО.

2.При данном оптимальном распределении студентов с четырех полей будет убрано 1149 центнеров картофеля.

Пример № 2

План перевозок:

Поставщики Аi	Потребители Вj:
	Запасы аi	Себестоимость	В1	В2	В3	В4
А1
А2
А3

Решение:

Проверяем на сбалансированность

Задача не сбалансированная. Введем фиктивного потребителя В₅ с потребностью в грузе, равной 200 ед. Стоимость перевозки для фиктивного потребителя определим равной нулю.

В качестве общей стоимости C_ij¹ будем брать сумму затрат на доставку единицы продукции C_ij из соответствующего пункта и ее себестоимость C_i в этом пункте.

C_ij¹=C_ij + C_i

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

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

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

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

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

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

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

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

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

Потребители Поставщики	В1	В2	В3	В4	В5	Ui
А1		350 4	8	50 -W		+W	U1 =-2
	6	9		0
А2		9	100 +W				200	-W 0	U2= -6
	5		10	4
А3		7	150	-W	100	+W 8	250 6	0	U3 =0
11
Vj	V1 =6	V2 =11	V3 =8	V4 =6	V5 = 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 по контуру.

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

Потребители Поставщики	В1	В2	В3	В4	В5	Ui
А1		350	-W				50 +W	U1 =-6
4	8	6	9		0
А2			9	150 +W			150	-W 0	U2= -6
	5	10	4
А3			+W	100	-W	150 8	250 6	0	U3 =0
7	11
Vj	V1 =10	V2 =11	V3 =8	V4 =6	V5 = 6	W=100

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

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

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

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

Потребители Поставщики	В1	В2	В3	В4	В5	Ui
А1		250 4	8	6	9	150 0	U1 =-3
А2		9	250 5	10	4	50 0	U2= -3
А3		100 7	11	150 8	250 6	0	U3 =0
Vj	V1 =7	V2 =8	V3 =8	V4 =6	V5 = 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.Суммарные затраты на изготовление и перевозку продукции:

ден. ед.