Розв’язування задач лінійного програмування за допомогою Excel

 

Спочатку розв’яжемо симплекс – методом за допомогою EXCEL економіко - математичну модель задачі планування виробництва, яка була першою сформульована у цьому розділі і вже розв’язана графічним методом у §2:

f = 200 х₁ + 300 х₂ (max)

.

Згідно з планом попереднього параграфу

1. Зведемо цю задачу лінійного програмування до канонічної форми. Ввівши додаткові змінні х₃, х₄, х₅, отримуємо

f = 200 х₁ + 300 х₂ (max)

Запишемо її у електронну симплекс – таблицю:

 

	A	B	C	D	E	F	G
	x1	x2	x3	x4	x5	b	b/aij

Тут окрім стандартних стовпців симплекс – таблиці введений ще стовпець b/aij, у якому далі буде перевірятись умова допустимості.

2. Симплекс – таблиця виявляється приведеною до базису А₃, А₄, А₅ опорного розв’язку. Це видно з того, що матриця такого розв’язку на стовпцях змінних х₃, х₄, х₅ є діагональною, а оцінки основних змінних дорівнюють нулю. Отже, початковий опорний розв’язок α₁ = (0; 0; 0; 0; 18; 30; 40), f (α₁) = 0.

3. Серед оцінок базису є додатні, тож згідно з ознакою оптимальності α₁ не є оптимальним і отже треба виконати крок симплекс – методу.

1) Вибираємо найбільшу додатну оцінку δ₂ = 300. Зафарбуємо її в улюблений колір (тут червоний). Тим самим обрані змінна х₂ і стовпець з номером 2 симплекс – таблиці.

2), 3) Елементи у стовпці 2 додатні, отже треба застосувати умову допустимості. У чарунок G2 електронної симплекс – таблиці введемо формулу = F2/B2, а далі скопіюємо (протягнемо) її у чарунки G3 і G4. В результаті дістанемо:

 

	A	B	C	D	E	F	G
	x1	x2	x3	x4	x5	b	b/aij

 

Мінімальне з отриманих значень Θ = 5 у чарунці G2. Зафарбуємо її бажано в той самий колір. Тим самим обрані рядок 1 (для якого саме і виконується умова допустимості) і ведучий елемент жорданова перетворення на перетині обраних рядка і стовпця у чарунку В2. Зафарбуємо також і його.

4) Жорданово перетворення: треба рядок 2 поділити на 20, а від кожного рядка з решти відняти отриманий, помноживши його на відповідне число у стовпці В. Задамо відповідні формули у стовпці В електронної симплекс – таблиці, а в решту скопіюємо з нього. Отже,

виокремимо нову симплекс – таблицю в діапазоні А7: G10. Надамо чарункам електронної таблиці таких значень:

	А	B	C	D	E	F	G
	←	=В2/$В$2	→	→	→	→
	←	=В3 – В7*$B$3	→	→	→	→
	←	=В4 – В7*$B$4	→	→	→	→
	←	=В5 – В7*$B$5	→	→	→	→

Тут символ $ задає абсолютну адресацію: замість $В$2 можна задати прямо 20, замість $В$3 – 10. В результаті дістанемо:

	A	B	C	D	E	F	G
	x1	x2	x3	x4	x5	b	b/aij
	0,5		0,05
			-0,5
	7,5		-0,75
			-15			-1500

 

5) Маємо симплекс – таблицю з новим набором основних змінних х₂, х₄, х₅ (іншими словами з новим базисом), новий опорний розв’язок (0; 5; 0; 50; 15), нове значення цільової функції f = 1500.

6) На цьому перший крок симплекс – методу завершується. Треба розпочати другий крок з аналізу оцінок змінних і далі повторити всі попередні пункти.

Другий крок. 1) У симплекс – таблиці, отриманій на першому кроці, залишилась одна додатна оцінка у чарунці А10 δ₁ = 50, зафарбуємо її. Тим обрані змінна х₁ і стовпець з номером 1 симплекс – таблиці.

2), 3) Елементи в обраному стовпці додатні, отже треба застосувати умову допустимості. У чарунок G7 електронної симплекс – таблиці введемо формулу = F2/B2 і скопіюємо її у чарунки G8 і G9. В результаті дістанемо:

 

	A	B	C	D	E	F	G
	x1	x2	x3	x4	x5	b	b/aij
	0,5		0,05
			-0,5				3,333333
	7,5		-0,75
			-15			-1500

 

Зафарбуємо мінімальне з отриманих значень Θ = 2 у чарунці G9. Зафарбуємо також на перетині обраних рядка і стовпця ведучий елемент жорданова перетворення у чарунці А9.

4) Жорданово перетворення: виокремимо нову симплекс – таблицю в діапазоні А12: G15. Надамо чарункам електронної таблиці таких значень:

 

	А	B	C	D	E	F	G
	=А7 – А14*$А$7	→	→	→	→	→
	=А8 – А14*$А$8	→	→	→	→	→
	=А9/$А$9	→	→	→	→	→
	=А10 – А14*$А$10	→	→	→	→	→

 

Звичайно, що спочатку діємо у рядку 14, а потім у решті. В результаті дістанемо:

 

	A	B	C	D	E	F	G
	x1	x2	x3	x4	x5	b	b/aij
			0,1		-0,06667
					-2
			-0,1		0,133333
			-10		-6,66667	-1600

 

5) Маємо симплекс – таблицю з новим набором основних змінних х₁, х₂, х₄ (іншими словами з новим базисом), новий опорний розв’язок (2; 4; 0; 20; 0), нове значення цільової функції f = 1600.

6) Нарешті всі оцінки не додатні. Згідно з теоремою 1 це означає, що розв’язок (2; 4; 0; 20; 0) і значення цільової функції f = 1600 є оптимальними. На цьому симплекс – метод завершує роботу.

Загалом процес обчислень виглядає так:

 

	A	B	C	D	E	F	G
	x1	x2	x3	x4	x5	b	b/aij
	0,5		0,05
			-0,5				3,333333
	7,5		-0,75
			-15			-1500
			0,1		-0,06667
					-2
			-0,1		0,133333
			-10		-6,66667	-1600

 

Відкинувши три останні додані змінні, дістаємо розв’язок початкової задачі х₁ = 2, х₂ = 4, той самий, що і графічним методом. Цей розв’язок можна отримати і використавши надбудову EXCEL “Пошук розв’язку”. Ця надбудова задачі лінійного програмування розв’язує симплекс – методом, проте відразу видає оптимальний розв’язок до заданої математичної моделі.

Спочатку запишемо дані задачі в електронну таблицю у форматі, схожому на формат симплекс – таблиці.

	A	B	C	D
	x1	х2	b

 

Тут у рядки 2,3,4 занесена матриця обмежень цієї задачі лінійного програмування, у рядку 5 до неї додані коефіцієнти цільової функції. Тепер додамо до цього у рядку 6 поточні значення змінних х₁, х₂ (зазвичай найбільш зручно х₁ = 1, х₂ = 1); у стовпці D відповідні значення лівих частин системи обмежень при поточних значеннях змінних. Тут у чарунці D2 задана формула =СУММПРОИЗВ(А2:В2;$А$6:$В$6), яка обчислює скалярний добуток масиву А2:В2 на масив А6:В6, тобто значення 10х₁ + 20х₂ при поточних значеннях змінних х₁ = 1, х₂ = 1. У чарунки D3:D5 цю формулу копіюємо. В результаті дістанемо:

	A	B	C	D
	х1	х2	b
			f=

 

У чарунці D5 тут значення цільової функції при поточних значеннях змінних, виділимо її і далі в термінології надбудови “Пошук розв’язку” будемо називати цільовою. Тепер час обрати Поиск решения у меню Сервис. (Якщо його нема в меню Сервис, то оберіть там команду Надстройки і у вікні діалогу Список надстроек встановіть прапорець Поиск решения). Адреса D5 з’явиться у полі Целевая ячейка вікна Поиск решения.

Після слова Равной: оберемо варіант максимальному значению. У поле Изменяя ячейки треба внести адресу змінних – діапазон А6:В6; виділимо його, коли курсор знаходиться у цьому полі, і ця адреса там з’явиться автоматично. У поле Ограничения треба внести систему обмежень. Натиснімо на кнопку Добавить, з’явиться наступне вікно діалогу:

Воно складається з трьох частин. У поле Ссылка на ячейку треба внести адресу чарунок, які містять значення лівих частин системи обмежень при поточних значеннях змінних, що підлягають обмеженню. Коли курсор знаходиться у цьому полі, виділимо чарунки D2:D4 і вони з’являться там. У центрі умова обмеження, яку треба вибрати із списку: в даному випадку це ≤. У поле Ограничение: треба внести його значення безпосередньо або адресу чарунки, де воно знаходиться. Коли курсор у цьому полі, виділимо чарунки С2:С4 і вони з’являться там. Тим самим задані три обмеження: 10х₁ + 20х₂ ≤ 100, 20х₁ + 10х₂ ≤ 100, 15х₁ + 15х₂ ≤ 90 одночасно. Натиснімо на Добавить, щоби прийняти ці обмеження і перейти до наступних. У системі обмежень ще залишилась умова х_j ≥ 0 (j = 1,2). Так само внесемо у поле Ссылка на ячейку чарунки А6:В6, у центрі виберемо ≥ із списку, у полі Ограничение безпосередньо з клавіатури задамо 0.

Натиснімо на ОК, щоби прийняти ці обмеження і повернутись до вікна Поиск решения.

Тепер у цьому вікні вся економіко – математична модель даної задачі лінійного програмування: адреса цільової функції, вибір максимуму або мінімуму, адреса змінних, система обмежень. Натиснемо на Выполнить.

Відповідь можна знайти безпосередньо у чарунках змінних А6:В6 х₁ = 2, х₂ = 4, той самий, що і раніше. Вікно Результаты поиска решения повідомляє, що розв’язок знайдений при заданих обмеженнях. Якщо обрати Восстановить исходное значение, у полі Тип отчёта обрати Результаты і натиснути ОК, то у таблиці даних відтворяться початкові значення чарунок, а на окремому листі буде створений наступний звіт, який ми побачимо, якщо натиснути на Отчёт по результатам 1

 

Microsoft Excel 11.0 Отчет по результатам
Рабочий лист: [Поиск.xls]Лист1
Отчет создан: 06.02.2010 13:00:35
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$D$5	f=
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$A$6	x1
	$B$6	x2

 

По суті це відповідь даної задачі, створена у EXCEL. Розглянемо ще один приклад застосування надбудови Поиск решения – транспортну задачу, що була сформульована у §1. Це досить специфічний приклад задачі лінійного програмування, для розв’язання якої зазвичай використовують не симплекс – таблицю, а дещо іншу таблицю, яку і називають транспортною. Перш за все запишемо таку таблицю для даної задачі на лист EXCEL:

 

	A	B	C	D	E
		М1	М2	М3
	Р1
	Р2
	Р3

 

Фактично це таблиця вартості перевезень, наведена в умові задачі, до якої додані рядок попиту пунктів призначення знизу і праворуч стовпець ваги вантажу, що треба вивезти з пунктів відправлення. Для змінних – ваги вантажу, запланованого для перевезення з пункту Р_i до пункту М_j (i, j = 1,2,3) – відведемо ще одну таблицю в діапазоні В8:D10, схожу на попередню. Як і раніше, зазвичай найбільш зручно у ці чарунки задати одиниці.

 

	A	B	C	D	E
		М1	М2	М3
	Р1
	Р2
	Р3
	Вартість

 

У чарунку В11 задамо формулу = СУММ(B8:B10) – це сумарна вага вантажу до пункту призначення М1: тут 3, оскільки всі змінні дорівнюють 1. (Можна виділити В11 і натиснути на ∑ (Автосумма) на стандартній панелі EXCEL і формула з’явиться там автоматично). Скопіюємо цю формулу у чарунки В12 і В13 для пунктів призначення М2 і М3. Аналогічно у чарунці Е8 формула =СУММ(B8:D8) – це сумарна вага вантажу з пункту відправлення Р1; скопіюємо цю формулу у чарунки Е9 і Е10 для Р2 і Р3. Рядок 6 під транспортною таблицею призначений для цільової функції, вартості в цій задачі (як це і у симплекс – таблиці). У чарунку В6 задамо формулу =СУММПРОИЗВ(B2:B4;B8:B10) – це вартість перевезень до М1 за даним планом перевезень, скопіюємо її у С6 і D6 для М2 і М3. У чарунку Е6 запишемо формулу = СУММ(B6:D6) – це значення цільової функції при поточних значеннях змінних, а Е6 в термінології надбудови “Пошук розв’язку” є цільовою чарункою. Виділимо її і тепер час обрати Поиск решения у меню Сервис.

 

 

У цьому вікні вся економіко – математична модель даної задачі лінійного програмування. А саме після слова Равной: обираємо варіант минимальному значению, тобто забезпечуємо вимогу, щоби загальна вартість перевезень була мінімальною. У поле Изменяя ячейки вносимо адресу змінних – діапазон В8:D10. У полі Ограничения (як і раніше, через вікно діалогу Добавление ограничений) виписана система обмежень цієї задачі, отримана у формульному вигляді в §1. Тут у першому рядку забезпечується вимога, щоби повністю був задоволений попит пунктів призначення; у третьому, щоби весь вантаж був вивезений з пунктів відправлення; у другому вимога невід’ємності змінних, тобто ваги вантажу. Натиснемо на Выполнить.

 

 

Вікно Результаты поиска решения повідомляє, що розв’язок знайдений при заданих обмеженнях. Оберемо Восстановить исходное значение і Результаты у полі Тип отчёта. Якщо тепер натиснути ОК, то у таблиці даних відтворяться початкові значення чарунок, а на окремому листі буде сформована відповідь, яку ми побачимо, якщо натиснути на

Отчёт по результатам 1.

 

 

Microsoft Excel 11.0 Отчет по результатам
Рабочий лист: [Поиск.xls]Лист2
Отчет создан: 06.02.2010 21:39:45
Целевая ячейка (Минимум)
	Ячейка	Имя	Исходное значение	Результат
	$E$6	Вартість		91,00000267
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$B$8	М1		3,000000667
	$C$8	М2
	$D$8	М3
	$B$9	М1		2,999999333
	$C$9	М2
	$D$9	М3		5,000000667
	$B$10	М1
	$C$10	М2
	$D$10	М3		10,00000033

 

Отже, х₁₁ = 3, х₂₁ = 3, х₃₁ = 0, х₁₂ = 9, х₂₂ = 0, х₃₂ = 0, х₁₃ = 0, х₂₃ = 5, х₃₃ = 10. У термінах початкової задачі це означає, що вага вантажу з Р1 до М1 3 т, з Р2 до М1 3 т, з Р3 до М1 0, з Р1 до М2 9 т, …; мінімальне можливе значення вартості дорівнює 91 грошовій одиниці.

 

Приклади

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

 

f = 3x₂ + x₁ (max)

.

 

Складемо відповідну електронну таблицю так, як у першому прикладі цього параграфу:

 

	A	B	C	D
	х1	х2	b
				=СУММПРОИЗВ(A1:B1;$A$5:$B$5)
				↓
			f=	↓

 

Дістанемо

	A	B	C	D
	х1	х2	b
			f=

 

Виділимо цільову чарунку D4 і оберемо Поиск решения у меню Сервис. Всю решту даних математичної моделі заносимо далі у це вікно. А саме після слова Равной: обираємо варіант максимальному значению, у поле Изменяя ячейки вносимо адресу змінних А5:В5.

У полі Ограничения (як і раніше, через вікно діалогу Добавление ограничений) виписана система обмежень цієї задачі: нерівності 2х₁ + 6х₂ ≤ 10, 3х₁ + 2х₂ ≤ 8 у рядку 2, умова невід’ємності змінних у рядку 1.

 

 

Натиснемо на Выполнить. Дістанемо:

 

Оберемо Восстановить исходное значение і Результаты у полі Тип отчёта у вікні Результаты поиска решения. Натиснувши на ОК, дістанемо відповідь, яку побачимо, якщо натиснути на Отчёт по результатам 1.

 

Microsoft Excel 11.0 Отчет по результатам
Рабочий лист: [Симплекс- много решений.xls]Лист1
Отчет создан: 07.02.2010 18:49:49
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$D$4	f=
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$A$5	х1		1,1
	$B$5	х2		1,3

Ніби – то все гаразд, але спробуємо розв’язати ту саму модель з іншими початковими значеннями змінних х₁ = 1, х₂ = 2. Відповідна електронна таблиця:

 

	A	B	C	D
	х1	х2	b
			f=

 

Виділимо цільову чарунку D4, оберемо Поиск решения у меню Сервис, всю решту даних математичної моделі заносимо далі у це вікно так само, як і раніше. Натиснемо на Выполнить і дістанемо:

 

 

Натиснувши на ОК, а потім на Отчёт по результатам 2, дістанемо відповідь:

 

Microsoft Excel 11.0 Отчет по результатам
Рабочий лист: [Книга1]Лист1
Отчет создан: 07.02.2010 15:45:25
Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$D$3	f=
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$A$4	х1		0,8
	$B$4	х2		1,4

 

Перший раз ми дістали х₁ = 1,1, х₂ = 1,3. Виявляється, що оптимальний розв’язок, який видає Поиск решения, залежить від початкових даних. Чи можливо таке насправді і як це збігається з теоремами, отриманими раніше? Розв’яжемо цю модель симплекс – методом.

1. Зведемо цю задачу до канонічної форми. Ввівши додаткові змінні х₃, х₄, отримуємо:

f = 3x₂ + x₁ (max)

.

Запишемо її у електронну симплекс – таблицю:

 

	A	B	C	D	E	F
	x1	x2	x3	x4	b	b/aij

 

2. Симплекс – таблиця виявляється приведеною до базису А₃, А₄ опорного розв’язку. Це видно з того, що матриця такого розв’язку на стовпцях змінних х₃, х₄ є діагональною, а оцінки основних змінних дорівнюють нулю.

3. Серед оцінок базису є додатні, тож згідно з ознакою оптимальності треба виконати крок симплекс – методу.

1) Вибираємо найбільшу додатну оцінку δ₂ = 3. Зафарбуємо її у червоний колір. Тим самим обрані змінна х₂ і стовпець з номером 2 симплекс – таблиці.

2), 3) Елементи у стовпці 2 додатні, отже треба застосувати умову допустимості. У чарунок F2 електронної симплекс – таблиці введемо формулу = E2/B2, а далі скопіюємо (протягнемо) її у чарунки F3 і F4. В результаті дістанемо:

 

	A	B	C	D	E	F
	x1	x2	x3	x4	b	b/aij
						1,666667

 

Мінімальне з отриманих значень Θ = 1,666667 у чарунці F2. Зафарбуємо його і ведучий елемент жорданова перетворення на перетині обраних рядка і стовпця у чарунці В2.

4) Жорданово перетворення: виокремимо нову симплекс – таблицю в діапазоні А6: F8. Надамо чарункам електронної таблиці таких значень:

 

	А	B	C	D	E	F
	←	=В2/$В$2	→	→	→
	←	=В3 – В6*$B$3	→	→	→
	←	=В4 – В6*$B$4	→	→	→

 

В результаті дістанемо:

 

	A	B	C	D	E	F
	0,333333		0,166667		1,666667
	2,333333		-0,33333		4,666667
			-0,5		-5

 

5) Маємо симплекс – таблицю з новим набором основних змінних х₂, х₄ , новий опорний розв’язок (0; 1,7; 0; 4,7), нове значення цільової функції f = 5.

6) Всі оцінки не додатні. Згідно з теоремою 1 це означає, що розв’язок і значення цільової функції є оптимальними. На цьому симплекс – метод завершує роботу. Відкидаючи додаткові змінні, дістаємо х₁ = 0, х₂ ≈ 1,7. Тут те ж саме значення цільової функції, що й отримане за допомогою надбудови Поиск решения, проте ще один новий розв’язок, тут безумовно опорний.

Зазначимо, що оцінка δ₁ = 0, отже цільова функція, виражена через вільні змінні х₁, х₃ має вигляд f = 5 – 0,5х₃. Тому, якщо обрати за нову основну змінну х₁, то хоча її значення і стане додатним замість нульового, але значення цільової функції f не зміниться і ми дістанемо новий оптимальний опорний розв’язок. Отже, виконаємо ще одне жорданове перетворення. Елементи у стовпці 1 додатні, отже треба застосувати умову допустимості. В результаті дістанемо:

 

	A	B	C	D	E	F
	x1	x2	x3	x4	b	b/aij
	0,333333		0,166667		1,666667
	2,333333		-0,33333		4,666667
			-0,5		-5
			0,214286	-0,14286
			-0,14286	0,428571
			-0,5		-5

 

Новий опорний розв’язок (1;2; 0; 0), f = 5. Відкидаючи додаткові змінні, дістаємо х₁ = 1, х₂ = 2. Отже, існують принаймні два різних оптимальних опорних розв’язка. Зазвичай зрозуміти, проаналізувати ситуацію найкраще геометрично. На рисунку 4 множина Ω допустимих розв’язків – це чотирикутник OABCD, обмежений осями координат і прямими L₁: 2х₁ + 6х₂ = 10 і L₂: 3х₁ + 2х₂ = 8. Лінія нульового рівня цільової функції L₀: f = х₁ + 3х₂ = 0 перетинає початок координат О(0;0) і перпендикулярна вектору нормалі N(1;3). Цей вектор перпендикулярний також і прямій L₁, бо вектор нормалі N₁(2;6) прямої L₁ є колінеарним вектору N(1;3): 2 ∙ N = N₁. Тому, як і на рисунку 2, існує нескінченна множина оптимальних розв’язків даної задачі – всі точки відрізка АВ. Вершини відрізка А(0;1,7) і В(2;1) – це якраз ті опорні розв’язки, які і були отримані симплекс – методом. Як виявляється, у такій задачі надбудова Поиск решения знаходить просто деякі точки на АВ залежно від початкових даних.

х₂

 

3 N(1;3)

 

1,7 A

L₁

 

B

Ω L₂

O 1 C х₁

2,7 5

L₀

 

Рисунок 4.

Розглянемо ще один приклад математичної моделі.

f = 3х₁ + 2х₂ (max)

.

Складемо відповідну електронну таблицю:

 

	A	B	C	D
	х1	х2	b
				=СУММПРОИЗВ(A1:B1;$A$4:$B$4)
		– 1		↓
			f=	↓

 

Дістанемо

 

	A	B	C	D
	х1	х2	b
		-1
			f=

 

 

Виділимо цільову чарунку D4 і оберемо Поиск решения у меню Сервис. Після слова Равной: обираємо варіант максимальному значению, у поле Изменяя ячейки вносимо адресу змінних А5:В5. У полі Ограничения: система обмежень цієї задачі: невід’ємність змінних у рядку 1, нерівність 2х₁ + 3х₂ ≥ 7 у рядку 2, 4х₁ – 2х₂ ≤ 7 у рядку 3.

Натиснемо на Выполнить. Дістанемо:

 

У вікні Результаты поиска решения повідомлення, що не відбулося збігу ітерацій, що і зрозуміло, бо надто великими є отримані результати: х₁ = 31317472, х₂ = 125269882, f = 3,44E+08 = 3,44∙10⁸. Навряд чи прибуток перевершив 10⁸, скоріше за все тут зовсім не існує розв’язка. Але чи так воно насправді? Розв’яжемо цю модель симплекс – методом.

1. Зведемо задачу до канонічної форми. Ввівши додаткові змінні х₃, х₄, отримуємо:

f = 3x₂ + 2x₁ (max)

.

Запишемо її у електронну симплекс – таблицю:

 

	A	B	C	D	E	F
	x1	x2	x3	x4	b	b/aij
			– 1
		– 7

2. На відміну від попередніх прикладів тут нема початкового опорного розв’язку: нема діагональної матриці. Насправді ж він є необхідним, щоби започаткувати симплекс – метод. Належний вигляд уже має стовпець змінної x₄, до неї треба додати ще одну. Це не може бути x₃ бо для такого опорного розв’язку x₃ = – 7, тобто він не є допустимим. Це не може бути і x₁. Справді, застосуємо умову допустимості, яка є необхідною і достатньою для того, щоби отриманий в результаті жорданова перетворення опорний розв’язок виявився допустимим. Тут min {7/4, 7/2} досягається у рядку 3, тобто якщо у якості ведучого рядка обрати необхідний нам другий, то ми знову отримаємо недопустимий опорний розв’язок. Залишилась змінна x₂, ведучий елемент жорданова перетворення у чарунці В2. Отже, виокремимо нову симплекс – таблицю в діапазоні А6: F8. Надамо чарункам електронної таблиці таких значень:

	А	B	C	D	E	F
	←	=В2/$В$2	→	→	→
	←	=В3 – В6*$B$3	→	→	→
	←	=В4 – В6*$B$4	→	→	→

 

В результаті дістанемо:

 

	А	B	C	D	E	F
	x1	x2	x3	x4	b	b/aij
	2/3		- 1/3		2 1/3
	4 2/3		- 1/3		9 1/3
	1 2/3		2/3		-4 2/3

 

Тут є додатна оцінка δ₃ = 2/3, а всі елементи стовпця С, окрім самої оцінки δ₃ недодатні.

Тому цільова функція не обмежена зверху (теорема 2, умова необмеженості цільової функції), тобто оптимального розв’язку даної задачі справді не існує. На рисунку 5 множина Ω допустимих розв’язків цієї задачі – це необмежений чотирикутник BACD, обмежений віссю координат Ох₂ і прямими L₁: 2х₁ + 3х₂ = 7 і L₂: 4х₁ – х₂ = 7. Лінія нульового рівня

х₂

B D

Ω L₂

A N(3;2)

L₀ C L₁

х₁

О

 

 

Рисунок 5

цільової функції L₀: f = 3х₁ + 2х₂ = 0 перетинає початок координат О(0;0) і

перпендикулярна вектору нормалі N(3;2). Як і на рисунку 3, при пересуванні у напрямку вектора N пряма, паралельна L₀ весь час буде перетинати область Ω, то цільова функція f не обмеж