Математическое программирование (стр. 2 из 3)

С 4 рядка последней симплекс-таблицы виписываем оптимальный план, где y₁=x₃, y₂=x₄, y₃=x₅, тоесть

Значение

отвечает значению 4881/14, что находится в 0 рядке планового столбика.

С экономической точки зрения нулевое значение переменной у₃ значит, что для минимальных издержек стоимость ресурсів R₃ должна равняться 0.

Таким образом, продукции P₁ и P₂ нужно производить 215/14 и 69/14 ед. соответственно. Максимальная прибыль при этом составит 4881/14 у.д.е.

Ответ:

3.4. Найти оптимальный план транспортной задачи.

Решение

Запишем условие задачи в экономическом виде на основании таблицы, где заданы пункты отправления и назначения, запасы и потребности [1, c. 135].

Пункты отправления	Пункты назначения				Запасы
Пункты отправления	B₁	B₂	B₃	B₄	Запасы
A₁	9	8	7	4	220
A₂	5	6	10	3	120
A₃	2	3	5	7	150
Потребности	200	200	140	180	720\490

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

1) Диагональный метод

Найдем опорный план диагональным методом [1, c. 140].

BA		1		2		3	4	a
		200		200		140	180
1	220	9		8		7	4	0
		200	20	–	0	+
2	120	5		6		10	3	–2
		120
3	150	2		3		5	7	–5
		60	+	90	–
4	230	0		0		0	0	–10
		50	+	180	–
b		9		8		10	10

Стоимость начального плана перевозки:

z₀ = 200 · 9+20 · 8+120 · 6+60 · 3+90 · 5+50 · 0+180 · 0 = 3310.

Для базисных клеток система потенциалов такая:

a₁+b₁=9; a₁+b₂=8;

a₂+b₂=6;

a₃+b₂=3; a₃+b₃=5;

a₄+b₃=0; a₄+b₄=0.

Поскольку количество переменных меньше, чем уравнений, то положим: a₁=0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c

a₁+b₃=0+10=10 > 7 [3]; a₁+b₄=0+10=10 > 4 [6];

a₂+b₁=–2+9=7 > 5 [2]; a₂+b₃=–2+10=8 ≤ 10; a₂+b₄=–2+10=8 > 3 [5];

a₃+b₁=–5+9=4 > 2 [2]; a₃+b₄=–5+10=5 ≤ 7;

a₄+b₁=–10+9=–1 ≤ 0; a₄+b₂=–10+8=–2 ≤ 0;

Для клетки A₁B₄ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(20, 90, 180)=20.

Переходим к следующей итерации.

B A		1		2		3	4	a
		200		200		140	180
1	220	9		8		7	4	0
		200	–	20	+
2	120	5		6		10	3	4
		0	+	120	–
3	150	2		3		5	7	1
		80	+	70	–
4	230	0		0		0	0	–4
		70	+	160	–
b		9		2		4	4

Стоимость 1 плана перевозки:

z₁ = 200 · 9+20 · 4+120 · 6+80 · 3+70 · 5+70 · 0+160 · 0 = 3190.

Для базисных клеток система потенциалов такая:

a₁+b₁=9; a₁+b₄=4;

a₂+b₂=6;

a₃+b₂=3; a₃+b₃=5;

a₄+b₃=0; a₄+b₄=0.

a₁+b₂=0+2=2 ≤ 8; a₁+b₃=0+4=4 ≤ 7;

a₂+b₁=4+9=13 > 5 [8]; a₂+b₃=4+4=8 ≤ 10; a₂+b₄=4+4=8 > 3 [5];

a₃+b₁=1+9=10 > 2 [8]; a₃+b₄=1+4=5 ≤ 7;

a₄+b₁=–4+9=5 > 0 [5]; a₄+b₂=–4+2=–2 ≤ 0;

Для клетки A₂B₁ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(200, 160, 70, 120)=70.

Переходим к следующей итерации.

BA		1		2		3	4	a
		200		200		140	180
1	220	9		8		7	4	0
		130	–	90	+
2	120	5		6		10	3	–4
		70	+	50	–
3	150	2		3		5	7	–7
		150
4	230	0		0		0	0	–4
		0	+	140	90	–
b		9		10		4	4

Стоимость 2 плана перевозки:

z₂ = 130 · 9+90 · 4+70 · 5+50 · 6+150 · 3+140 · 0+90 · 0 = 2630.

Для базисных клеток система потенциалов такая:

a₁+b₁=9; a₁+b₄=4;

a₂+b₁=5; a₂+b₂=6;

a₃+b₂=3;

a₄+b₃=0; a₄+b₄=0.

a₁+b₂=0+10=10 > 8 [2]; a₁+b₃=0+4=4 ≤ 7;

a₂+b₃=–4+4=0 ≤ 10; a₂+b₄=–4+4=0 ≤ 3;

a₃+b₁=–7+9=2 ≤ 2; a₃+b₃=–7+4=–3 ≤ 5; a₃+b₄=–7+4=–3 ≤ 7;

a₄+b₁=–4+9=5 > 0 [5]; a₄+b₂=–4+10=6 > 0 [6];

Для клетки A₄B₂ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(50, 130, 90)=50.

Переходим к следующей итерации.

B A		1		2		3	4	a
		200		200		140	180
1	220	9		8		7	4	0
		80	–	140	+
2	120	5		6		10	3	–4
		120
3	150	2		3		5	7	–1
		0	+	150	–
4	230	0		0		0	0	–4
		50	+	140	40	–
b		9		4		4	4

Стоимость 3 плана перевозки:

z₃ = 80 · 9+140 · 4+120 · 5+150 · 3+50 · 0+140 · 0+40 · 0 = 2330.

Для базисных клеток система потенциалов такая:

a₁+b₁=9; a₁+b₄=4;

a₂+b₁=5;

a₃+b₂=3;

a₄+b₂=0; a₄+b₃=0; a₄+b₄=0.

a₁+b₂=0+4=4 ≤ 8; a₁+b₃=0+4=4 ≤ 7;

a₂+b₂=–4+4=0 ≤ 6; a₂+b₃=–4+4=0 ≤ 10; a₂+b₄=–4+4=0 ≤ 3;

a₃+b₁=–1+9=8 > 2 [6]; a₃+b₃=–1+4=3 ≤ 5; a₃+b₄=–1+4=3 ≤ 7;

a₄+b₁=–4+9=5 > 0 [5];

Для клетки A₃B₁ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(80, 40, 150)=40.

Переходим к следующей итерации.

BA		1		2		3	4	a
		200		200		140	180
1	220	9		8		7	4	0
		40	–	0	+	180
2	120	5		6		10	3	–4
		120
3	150	2		3		5	7	–7
		40	+	110	–
4	230	0		0		0	0	–10
		90	+	140	–
b		9		10		10	4

Стоимость 4 плана перевозки:

z₄ = 40 · 9+180 · 4+120 · 5+40 · 2+110 · 3+90 · 0+140 · 0 = 2090.

Для базисных клеток система потенциалов такая: