Завдання 2. Симплексний метод розв'язання задач лінійного програмування

Приклад 2.1. В господарстві для вирощування кукурудзи на зерно та ячменю виділено 400 га ріллі, 18000 людино-годин та 1800 ц мінеральних добрив. Вихід концентрованих кормів та затрати виробничих ресурсів (в розрахунку на 1 га) наведені нижче:

Показники	Кукурудза на зерно	Ячмінь
Затрати праці, людино-годин	50	30
Внесення мінеральних добрив, ц	6	3
Вихід кормів, ц к. од	90	50

Знайти посівні площі зернофуражних культур для отримання максимальної кількості концентрованих кормів.

Розв'язання. Для формулювання економіко-математичної моделі задачі введемо такі позначення:

х₁ - площа кукурудзи на зерно, га

х₂ - площа ячменю, га

Z_max – обсяг виробництва кормів, ц к. од.

Тоді умови задачі в математичній формі можна записати так:

1. Обмеження щодо використання ріллі:

х₁ + х₂ < 400

2. Обмеження щодо використання трудових ресурсів:

50х₁ + 30х₂ < 18000

3. Обмеження щодо використання мінеральних добрив:

6х₁ + 3х₂ < 1800

4. Обмеження на знак змінних:

х₁ 0, х₂ 0

Критерій оптимальності – виробництво максимальної кількості концентрованих кормів -

Z_max = 90х₁ + 50х₂

Запишемо задачу в канонічній формі, тобто перетворимо нерівності в системі обмежень в рівняння. Для цього в ліву частину кожної нерівності введемо по одній невід'ємній додатковій змінній, які в умовах даної задачі мають такий економічний зміст:

S₁ - кількість невикористаної площі ріллі, га;

S₂ - кількість невикористаних трудових ресурсів,

людино - годин;

S₃ - кількість невикористаних мінеральних добрив, ц.

В цільову функцію Z_max додаткові змінні вводяться з нульовою оцінкою. Тоді,

Z_max = 0 - ( - 90 х₁ - 50 х₂)

х₁ + х₂ + S₁ = 400

50 х₁ + 30 х₂+ S₂ = 18000

6 х₁ + 3 х₂ + S₃ = 1800

х₁ > 0, х₂ > 0; S₁ > 0; S₂ > 0; S₃ > 0;

Якщо змінні х₁ та х₂ прирівняти до нуля, то отримуємо допустимий базисний розв'язок задачі: х₁ = 0, х₂ = 0, S₁ = 400,

S₂ = 18000, S₃ = 1800 та _max = 0. В даному випадку х₁ та х₂, називаються небазисними змінними, а S₁, S₂, та S₃ - базисними змінними.

Розв'язання задачі продовжимо в симплексних таблицях, записавши в симплексну таблицю 1 отриманий допустимий базисний розв'язок задачі .

Симплексна таблиця 1

Базисні змінні	Значення базисних змінних	х1	х2	S1	S2	S3	L
S1	400	1	1	1	0	0	400
S2	18000	50	30	0	1	0	360
S3	1800	6	3	0	0	1	300
max	0	-90	-50	0	0	0

Умови оптимальності розв'язку задач симплексним методом:

1. При знаходженні максимального значення цільової функції розв'язок задачі буде оптимальним, якщо всі небазисні змінні в _max - рядку мають невід'ємні коефіцієнти або дорівнюють нулю (t > 0).

2. При знаходженні мінімального значення цільової функції розв'язок задачі буде оптимальним, якщо всі небазисні змінні в _min - рядку мають від'ємні значення або дорівнюють нулю ( t < 0).

В симплексній таблиці 1 небазисні змінні х₁ та х₂ в Z - рядку мають від'ємні коефіцієнти ( відповідно -90 та -50 ), тому розв'язок задачі не оптимальний.

Цільова функція буде наближатись до екстремального значення тоді, коли в базисний розв'язок задачі буде введена небазисна змінна, яка в Z-рядку має від'ємний коефіцієнт, причому тим скоріше, чим більший за абсолютним значенням (модулем) цей від'ємний коефіцієнт. В даному випадку цією небазисною змінною є змінна х₁ (-90). Стовпчик симплексної таблиці, в якій знаходиться така змінна, називається розв'язуючим. Для того, щоб в розв'язок задачі ввести цю змінну (х₁), потрібно з розв'язку вивести одну з базисних змінних ( S₁, S₂ або S₃). Для цього визначимо відношення значень базисних змінних до додатних елементів розв'язуючого стовпчика:

_{min {400 / 1= 400; 18000 / 50 = 360 ; 1800 / 6 = 300 } = 300}

Змінною, яка виводиться з базисного розв'язку, буде та, для якої розраховане відношення буде мінімальним. В симплексній таблиці 1 мінімальне відношення (300) належить 3-му рядку, якому відповідає змінна S₃. Такий рядок називається розв'язуючим.

Елемент симплексної таблиці на перетині розв'язуючого стовпчика та розв'язуючого рядка називається розв'язуючим (6).

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

1. Формування розв'язуючого рівняння (рядка):

попередній розв'язуючий рядок

новий розв'язуючий рядок = 

розв'язуючий елемент

Новий 3-й рядок = (1800630 01) / 6 = (30010.5000.167)

2. Формування всіх інших рівнянь (рядків), включаючи і Z-рівняння:

Новий рядок = попередній рядок - (новий розв'язуючий рядок)  (коефіцієнт розв'язуючої колонки попереднього рядка)

1-й рядок
Попередній 1-й рядок -		(400	1		1		1		0		0)-
новий розв'язуючий рядок		-(300	1		0.5		0		0		0.167)(1)
 (1) = новий 1-й рядок		=(100	0		0.5		1		0		-0.167)
2-й рядок
Попередній 2-й рядок -	(18000			50		30		0		1		0) -
новий розв'язуючий рядок	-(300			1		0.5		0		0		0.167)  (50)
 (50) = новий 2-й рядок	=(3000			0		5		0		1		- 8.333)
Z рядок
Попередній Z рядок -	(0			-90		-50		0		0		0) -
новий розв'язуючий рядок	-(300			1		0.5		0		0		0.167) х (-90)
 (-90) = новий Z - рядок	=(27000			0		-5		0		0		15)

Нова симплексна таблиця має такий вигляд (табл. 2). Зазначимо, що в базисний розв'язок замість змінної S₃ введена змінна Х₁.

Симплексна таблиця 2

Базисні змінні	Значення базисних змінних	Х1	Х2	S1	S2	S3	L
S1	100	0	0.5	1	0	-0.167	200
S2	3000	0	5	0	1	-8.333	600
Х1	300	1	0.5	0	0	0.167	600
Zmax	27000	0	-5	0	0	15

В симплексній таблиці 2 одержано новий базисний розв'язок: Z_max = 27000,

Х₁ = 300, Х₂ = 0, S₁ = 100, S₂ = 3000, S₃ = 0.

Значення цільової функції збільшилось з 0 до 27000. Це пояснюється тим, що в новому розв'язку площа кукурудзи на зерно становить 300 га (Х₁ = 300), кожний з яких дає 90 ц к. од. Тому значення цільової функції дорівнює

Z = 90  300 = 27000.

В зв'язку з тим, що небазисна змінна х₂ в Z-рядку має від'ємний коефіцієнт (-5), базисний розв'язок у симплексній таблиці 2 не оптимальний.

Продовжимо розв'язання задачі. В симплексній таблиці 2 стовпчик "Х₂" є розв'язуючим. Визначимо відношення значень базисних змінних до додатних елементів розв'язуючого стовпчика:

_{min {100 / 0.5 = 200; 3000 / 5 = 600; 300 / 0,5 = 600} = 200} ,

тому до нового базисного розв'язку замість S₁ вводимо Х₂. Розв'язуючим елементом симплексної таблиці 2 буде 0.5. Пошук нового базисного розв'язку здійснюємо знову за допомогою обчислювальних операцій методу Жордана-Гаусса:

Новий 1 -й рядок

(10000.51 0- 0.167) / 0,5 = (2000120- 0.333)

Новий 2-й рядок
Попередній 2-й рядок -	(3000	0	5	0	1	- 8.333) -
-новий розв'язуючий рядок	-(200	0	1	2		0 - 0.333)  (5)
 (5) = новий 2-й рядок	=(2000	0	0	-10	1	- 6.667)
Новий 3-й рядок
Попередній 3-й рядок -	(300	1	0.5	0	0	0.167) -
-новий розв'язуючий рядок	-(200	0	1	2	0	- 0.333  (0.5)
 (0.5) = новий 3-й рядок	=(200	1	0	-1	0	0.333)
Новий Z рядок
Попередній Z рядок -	(27000	0	-5	0	0	15) -
-новий розв'язуючий рядок	-(200	0	1	2	0	- 0.333)  (-5)
 (-5) = новий Z - рядок	=(28000	0	0	10	0	13.333)

Запишемо симплексну таблицю 3.

Симплексна таблиця 3

Базисні змінні	Значення базисних змінних	Х1	Х2	S1	S2	S3
Х2	200	0	1	2	0	-0.333
S2	2000	0	0	-10	1	-6.667
Х1	200	1	0	-1	0	0.333
Zmax	28000	0	0	10	0	13.333

В симплексній таблиці 3 маємо новий базисний розв'язок: Z = 28000,

х₁ = 200, х₂ = 200, S₁ = 0, S₂ = 2000, S₃ = 0. В Z_max-рядку відсутні від'ємні елементи, тому отриманий базисний розв'язок є оптимальним. Розв'язання задачі закінчено.

Висновки. Для виробництва максимальної кількості концентрованих кормів в господарстві потрібно вирощувати кукурудзу на зерно 200 га (х₁=200) та ячменю 200 га (х₂=200). Площа ріллі та мінеральні добрива використовуються повністю (S₁=0, S₃=0), а невикористані трудові ресурси становлять 2000 людино-годин (S₂=2000). Кількість кормів дорівнює 28000 ц к.од. (Z_max=28000).

Зауваження 1. Якщо розв'язуючий стовпчик має тільки від'ємні коефіцієнти і не можна знайти розв'язуючий рядок, то цільова функція не обмежена зверху (при знаходженні максимуму цільової функції) або знизу (при знаходженні мінімуму цільової функції) на множині допустимих розв'язків. Треба змінити умови задачі.

Зауваження 2. Якщо при визначенні розв'язуючого стовпчика в Z - рядку є однакові коефіцієнти, то вибирається будь-який з них.

Зауваження 3. Якщо при визначенні розв'язуючого рядка є однакові симплексні відношення, то вибирається будь-яке з них.

З

Х₁

адачі для контрольної роботи

Задача 2. Для вирощування озимої пшениці, кукурудзи на зерно та ячменю виділено 400 га ріллі, 24000 людино-годин трудових ресурсів та 1600 ц мінеральних добрив. Урожайність, затрати праці та мінеральних добрив наведені в таблиці 2.1.

Таблиця 2.1

С.-г. культури	Варіанти *)	Затрати праці на 1 га, людино-годин	Внесення мінеральних добрив на 1 га, ц	Урожайність, ц з 1 га
Озима пшениця	Для всіх варіантів	40	5	50
Кукурудза на зерно	0	40	4	40
	1	50	5	50
	2	60	8	64
	3	75	10	80
	4	80	4	60
	5	40	5	45
	6	50	8	59
	7	60	10	70
	8	75	4	55
	9	80	5	65
Ячмінь	0	20	2	28
	1	24	2.5	31
	2	25	4	36
	3	30	2	33
	4	32	2.5	35
	5	20	4	33
	6	24	2	30
	7	25	2.5	32
	8	30	4	38
	9	32	2	34

*) Варіант технології вирощування кукурудзи на зерно вибирається за передостанньою цифрою шифру (номера залікової книжки), Р, а варіант технології вирощування ячменю - за кінцевою цифрою шифру, К..

Визначити посівні площі сільськогосподарських культур з метою максимального виробництва зерна.