Типовой расчет №1 «Линейное программирование» (стр. 4 )

С учетом таблицы соответствия базисных переменных одной задачи свободным переменным другой, и, наоборот

X1	X2	X3	X4	X5	X6
Y3	Y4	Y5	Y6	Y1	Y2

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

i	Баз.	С баз.	А0	0	6	0	0	0	0
A1	A2	A3	A4	A5	А6
1	А2	6	7/3	0	1	-2/3	0	-1	0
2	А4	0	5	0	0	-2	1	-3	0
3	А6	0	1	0	0	-1	0	-1	1
4	А1	0	2/3	1	0	-1/3	0	0	0
5			0=14	∆1=0	∆2=0	∆3=-4	∆4=0	∆5=-6	∆6=0

x1=∆3=-(-4)=4

x2=∆4=0

x3=∆5=-(-6)=6

x4= ∆6=0

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

i	Баз.	С баз.	А0	2	0	1	2
A1	A2	A3	A4
1	А1	2	4	1	1	0	1
2	А3	1	6	0	2	1	1
3			L0=14	∆1=0	∆2=4	∆3=0	∆4=1

Переменные y1, y2 двойственной задачи соответствуют искусственным переменным x5, x6 исходной задачи, в последней симплекс-таблице соответствующие столбцы уже исключены, потому указать непосредственно из таблицы решение для прямой задачи решение двойственной невозможно.

Задача 3

Транспортная задача задана таблицей

вj ai	в1	в2	в3	в4	Запасы
а1	4	а	3	1	40
а2	5	9	в	2	10с
а3	2	5	а	с	50
Потребности	10с	30	20	30	90+10с

Найти базисную перевозку методом минимального элемента. Найти оптимальное решение методом потенциалов.

Вариант 7: а=8; в=2; с=7.

Получаем таблицу:

вj ai	в1	в2	в3	в4	Запасы
а1	4	8	3	1	40
а2	5	9	2	2	70
а3	2	5	8	7	50
Потребности	70	30	20	30	160 150

Решение:

Проверим условие разрешимости транспортной задачи: .

40+70+50=160≠150=70+30+20+30

Условие разрешимости транспортной задачи не выполнено. Вводим фиктивного потребителя в5 мощностью 10 ед. Стоимости поставки к этому фиктивному потребителю ото всех поставщиков примем равной нулю.

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4	8	3	1	0	40
а2	5	9	2	2	0	70
а3	2	5	8	7	0	50
Потребности	70	30	20	30	10	160 150

Обозначим xij – количество груза, перевозимого из пункта аi в пункт вj:

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

при ограничениях:

.

Найдем исходное опорное решение по методу минимальной стоимости. Для этого заполним распределительную таблицу. Минимальная стоимость перевозок 1, заполним соответствующую ячейку (1;4) объемом перевозки 30=min(30;40):

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4	8	3	1 30	0	40
а2	5	9	2	2	0	70
а3	2	5	8	7	0	50
Потребности	70	30	20	30	10	160 160

Исключаем из рассмотрения 4-го потребителя, так как его потребности полностью удовлетворены.

Дальше минимальная стоимость перевозки равна 2. Она соответствует ячейкам (3;1) и (2;4). Заполним (3;1) объемом перевозки 50=min(50;70):

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4	8	3	1 30	0	40
а2	5	9	2	2	0	70
а3	2 50	5	8	7	0	50
Потребности	70	30	20	30	10	160 160

Исключаем из рассмотрения третьего поставщика, т. к.его запасы полностью использованы.

Далее минимальная стоимость также 2 в ячейке (2;4) заполним ее перевозкой 20=min(20;70)

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4	8	3	1 30	0	40
а2	5	9	2 20	2	0	70
а3	2 50	5	8	7	0	50
Потребности	70	30	20	30	10	160 160

Исключаем из рассмотрения третьего потребителя, т. к. его потребности полностью удовлетворены. Среди оставшихся в рассмотрении ячеек минимальная стоимость равна 4, ячейку (1;1) заполним 10=min(70-50;40-30):

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4 10	8	3	1 30	0	40
а2	5	9	2 20	2	0	70
а3	2 50	5	8	7	0	50
Потребности	70	30	20	30	10	160 160

Первого поставщика исключим из рассмотрения, т. к. его запасы исчерпаны полностью. Из оставшихся в рассмотрении ячеек минимальная стоимость перевозки 5 в ячейке (2;1), заполним её 10=min(70-50-10;70-20), получаем:

вj ai	в1	в2	в3	в4	в5	Запасы
а1	4 10	8	3	1 30	0	40
а2	5 10	9	2 20	2	0	70
а3	2 50	5	8	7	0	50
Потребности	70	30	20	30	10	160 160

Потребителя номер 1 из рассмотрения исключаем, т. к. его потребности полностью удовлетворены. Осталась одна ненулевая стоимость перевозки 9, ее ячейку (2;2) заполним 30=min(30: 70-10-20)