Схематично опишіть абстрактне зображення рівнів системи

Найбільш неоптимальним є стовбець, що відповідає х2.

Визначимо ключовий рядок:

min (300 : 65 , 160 : 40 , 2200 : 250 , 34 : 1/2 ) = 4

Тобто ключовий рядок є другий. А ключовий елемент 40.

Отримуємо нову симплекс таблицю:

 

С	Базис	В	6	16	0	0	0	-М
			x1	x2	x3	x4	x5	x6
0	x3	40	0	0	1	-13/8	0	9/80
16	x2	4	0	1	0	1/40	0	-1/400
0	x5	1200	0	0	0	-25/4	1	-7/8
6	x1	32	1	0	0	-1/80	0	1/160
F(X2)		256	0	0	0	13/40	0	-1/400+M

 

Т.я. всі значення індексного рядка більше або дорівнює нулю, то дана симплекс-таблиця є оптимальною. Тобто маємо наступний розв'язок:

x1 = 32

x2 = 4

F(X) = 16•4 + 6•32 = 256

 

Задача 2.

 

Заводи деякої автомобільної фірми розташовані в містах А, В і С. Основниє центри розподілу продукції зосереджені в містах D і E. Обсяги виробництва вказаних трьох заводів дорівнюють 1000, 1300 і 1200 автомобілів щоквартальні. Величини квартального попиту в центрах розподілу складають 2300 і 1400 автомобілів відповідно. Вартості перевезення автомобілів по залізниці по кожному з можливих маршрутів наведені в таблиці.

Таблиця

Вартість перевезення автомобілів,г.о./шт.

	D	E
А	80	215
В	100	108
С	102	68

За кожен автомобіль, що недопостачається до розподільчих центрів D і E запроваджено штрафи 200 і 300 г.о. відповідно. Крім того, постачання із заводу А до розподільчого центру E не плануються взагалі.

Побудуйте математичну модель, що дозволяє визначити кількість автомобілів, що перевозять з кожного заводу в кожен центр розподілу, так, щоб загальні транспортні витрати були мінімальні.

 

Розв'язок:

 

Нехай змінні xij – це кількість автомобілів, що перевозяться з і-го заводу до j-го пункту споживання.

Перевіримо збалансованість задачі:

(1000+1300+1200)<(2300+1400)

Тобто задача незбалансована, оскільки попит на автомобілі перевищує обсяг їх виробництва. Для встановлення балансу вводимо фіктивний завод з обсягом виробництва 200 одиниць, запровадивши штрафи 200 і 300 г.о. за кожен автомобіль, що недопостачається до розподільчих центрів D і E.

Т.я. постачання із заводу А до розподільчого центру E не плануються взагалі, то введемо максимальну вартість перевезення 1000 г.о./шт.

Складемо розподільчу таблицу:

Заводи	Центри розподілу		Обсяг виробництва, одиниць
	D	E
А	80	1000	1000
В	100	108	1300
С	102	68	1200
Фіктивний завод	200	300	200
Попит, одиниць	2300	1400

 

Складемо математичну модель задачі:

 

 

За допомогою методу північно-західного кута знаходимо опорний план. Суть методу полягає у тому, що розподіл починаємо з верхнього лівого кута та ставимо в ньому значення, що відповідає найменшему з чисел ai, або bj. Потім, виокремлюють або рядок, або стовпець, потреби якого повністю задоволені. Поступово закриваємо усі потреби та розподіляємо запаси. Розподіл прямує до правого нижнього кута.

Заводи	Центри розподілу		Обсяг виробництва, одиниць
	D	E
А	80 1000	1000	1000
В	100 1300	108	1300
С	102	68 1200	1200
Фіктивний завод	200	300 200	200
Попит, одиниць	2300	1400

Підрахуємо кількість зайнятих клітин таблиці, їх 4, а повинно бути m + n - 1=5. Тобто опорний план є вирождений.

Значенні цільової функції для цього плану:

F(x) = 80*1000 + 100*1300 + 68*1200 + 300*200 = 351600

Будуємо новий план.

Заводи	Центри розподілу		Обсяг виробництва, одиниць
	D	E
А	80	1000 1000	1000
В	100 1300	108	1300
С	102 1000	68 200	1200
Фіктивний завод	200	300 200	200
Попит, одиниць	2300	1400

У результаті отримали невирождений план, т.я. кількість зайнятих клітин дорівнює 5.

Цільова функція:

F(x) = 1000*1000 + 100*1300 + 102*1000 + 68*200 + 300*200 = 1305600

Перевіримо оптимальність отриманого опорного плану. Знаходимо попередні потенціали ui, vj за зайнятими клітинами таблиці, в яких ui + vj = cij, вважаючи, що u1 = 0.

u1 + v2 = 1000; 0 + v2 = 1000; v2 = 1000

u3 + v2 = 68; 1000 + u3 = 68; u3 = -932

u3 + v1 = 102; -932 + v1 = 102; v1 = 1034

u2 + v1 = 100; 1034 + u2 = 100; u2 = -934

u4 + v2 = 300; 1000 + u4 = 300; u4 = -700

 

	v1=1034	v2=1000
u1=0	80	1000[1000]
u2=-934	100[1300]	108
u3=-932	102[1000]	68[200]
u4=-700	200	300[200]

 

Опорний план не є оптимальним, т.я. існують оцінки вільних клітин, для яких ui + vj > cij

(1;1): 0 + 1034 > 80; ∆11 = 0 + 1034 - 80 = 954

(4;1): -700 + 1034 > 200; ∆41 = -700 + 1034 - 200 = 134

max(954,134) = 954

Найбільш неоптимальна клітинка (1; 1).

Побудуємо цикл. В клітинку (1;1) поставимо знак «+», а в інших вершинах багатокутника знаки, що чередуються, «-», «+», «-».

Цикл отриманий в таблиці (1,1 → 1,2 → 3,2 → 3,1).

 

Заводи	Центри розподілу		Обсяг виробництва, одиниць
	D	E
А	80 [+]	1000 [-]1000	1000
В	100 1300	108	1300
С	102 [-]1000	68 [+]200	1200
Фіктивний завод	200	300 200	200
Попит, одиниць	2300	1400

 

Де стоїть знак «+» додаємо значення 1000, а де стоїть «-» - віднімаємо. Побудуємо еновий план.

Заводи	Центри розподілу		Обсяг виробництва, одиниць
	D	E
А	80 1000	1000	1000
В	100 1300	108 0	1300
С	102	68 1200	1200
Фіктивний завод	200	300 200	200
Попит, одиниць	2300	1400

Перевіримо оптимальність опорного плану:

u1 = 0.

u1 + v1 = 80; 0 + v1 = 80; v1 = 80

u2 + v1 = 100; 80 + u2 = 100; u2 = 20

u2 + v2 = 108; 20 + v2 = 108; v2 = 88

u3 + v2 = 68; 88 + u3 = 68; u3 = -20

u4 + v2 = 300; 88 + u4 = 300; u4 = 212

	v1=80	v2=88
u1=0	80[1000]	1000
u2=20	100[1300]	108[0]
u3=-20	102	68[1200]
u4=212	200	300[200]

 

Опорний план є неоптимальним, так як існують оцінки вільних клітин, для яких ui + vj > cij

(4;1): 212 + 80 > 200; ∆41 = 212 + 80 - 200 = 92

У клетинку (4;1) поставимо знак «+», а в інших вершинах багатокутника знаки, що чередуються, «-», «+», «-».

 

Заводи	Центри розподілу		Обсяг виробництва, одиниць
	D	E
А	80 1000	1000	1000
В	100 [-]1300	108 [+]	1300
С	102	68 1200	1200
Фіктивний завод	200 [+]	300 [-]200	200
Попит, одиниць	2300	1400

 

Отримуємо новий опорний план.

Заводи	Центри розподілу		Обсяг виробництва, одиниць
	D	E
А	80 1000	1000	1000
В	100 1100	108 200	1300
С	102	68 1200	1200
Фіктивний завод	200 200	300	200
Попит, одиниць	2300	1400