МЕТОДИЧНІ ВКАЗІВКИ до виконання розрахункової роботи з навчальної дисципліни “Економіко-математичні методи та моделі оптимізаційні методи та моделі”

Приклад 2.

1. Для того, щоб задачу можна було розв’язати симплексним методом, необхідно, щоб вона була представлена в канонічному вигляді (усі основні обмеження є рівняннями). Якщо в системі обмежень є обмеження-нерівності, то до лівої частини обмежень типу «» додаємо додаткові невід’ємні невідомі, а від лівих частин обмежень типу «» віднімаємо додаткові невід’ємні невідомі. Якщо права частина обмеження від’ємна, то множимо все обмеження на (-1).

Отже, канонічна (основна) форма запису матиме наступний вигляд:

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

Отже, базисні змінні – змінні, що відповідають умовам:

1) перед ними стоїть коефіцієнт +1;

2) ці змінні стоять лише в одному рівнянні, причому різні змінні стоять в різних рівняннях.

Всі інші змінні системи називаються вільними.

Якщо всім вільним змінним надати значення «0» і обчислити базисні, то ми отримаємо частинний розв’язок який називається базисним.

Опорним розв’язком системи лінійних алгебраїчних рівнянь називають невід’ємні базисні розв’язки даної системи обмежень.

– вільні змінні;

– базисні змінні.

Опорний розв’язок (план): (0; 0; 10; 11; 13).

2. Подальшу перевірку опорного плану на оптимальність здійснюють за допомогою симплекс-таблиці (табл. 5).

Таблиця 5

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

Базисні змінні БЗ	Коефіцієнти при базисних змінних Сб	Значення БЗ в опорному розв’язку Ао						=
4	5	0	0	0
	0	10	2	[3]	1	0	0	10/3=3,3
	0	11	1	1	0	1	0	11/1=11
	0	13	3	3	0	0	1	13/3=4,3
Значення цільової функції при даному опорному розв’язку	0	-4	-5	0	0	0	X
Записуємо індексний рядок початкової симплекс-таблиці . Дана задача на пошук цільової функції, тому критерієм оптимальності розв’язку є відсутність від’ємних оцінок у індексному рядку. Обирається найбільше по модулю від’ємне значення серед оцінок змінних, якщо задача на , у нашому випадку це значення -5. Обраний стовпчик відповідає невідомій, що вводиться в базис, називається ключовим стовпчиком. Розраховуємо значення симплексних відношень =: Визначаємо замість якої змінної введемо змінну , для цього числа в стовпчику Ао поділимо на додатні числа, що стоять в стовпчику : обирається найменше серед значень 10/3, відповідно вводиться нова базисна змінна , замість змінної . Рядок, який відповідає цьому найменшому відношенню, називається ключовим рядком. На перетині ключового рядка і ключового стовпця знаходять ключовий (генеральний) елемент. За допомогою метода Жордана-Гаусса переходимо до нової симплекс-таблиці. Для зручності робимо одиницю на місці ключового елементу (значення 3), тобто ділимо весь рядок на 3.
	5	10/3	2/3	[1]	1/3	0	0	Весь рядок/3
	0	11	1	1	0	1	0
	0	13	3	3	0	0	1
	0	-4	-5	0	0	0
Стовпчик Ао: : ; : ; : і т.д.
	5	10/3	2/3	[1]	1/3	0	0	10/3*3/2=5
	0	23/3	1/3	0	-1/3	1	0	23/3*3/1=23
	0	3	[1]	0	-1	0	1	3/1=3
	50/3	-2/3	0	5/3	0	0	X
Від’ємна оцінка є =-2/3, необхідно зробити перетворення.
	5	4/3	0	1	1	0	-2/3
	0	20/3	0	0	0	1	-1/3
	4	3	1	0	-1	0	1
	56/3	0	0	1	0	2/3	Х