Завдання для індивідуальної та самостійної роботи Розв‘язати задачу лінійного програмування графічним методом (max, min):

2.01 2.02

2.03 2.04

5. 2.06

2.07 2.08

2.09 2.10

2.11 2.12

2.13 2.14

2.17

2.18.

2.19 2.20

3. Симплекс-метод розв’язування задачі лінійного програмування

Симплексний метод, або метод послідовного поліпшення плану, полягає в послідовному переході від одного опорного плану до іншого так, що значення лінійної форми весь час збільшується. Оскільки число опорних планів задачі скінчене, то за скінчене число кроків метод дає змогу знайти оптимальний план (якщо він існує) або впевнитись, що лінійна форма на множині планів необмежена (якщо оптимальний план не існує). Для роботи методу повинен бути відомий початковий опорний план.

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

	с1	с2	. . . .	сn
Cб	x1	x2	. . . .	xn	bi	хбаз
	a11 a21 . . . . am1	a12 a22 . . . . am2	. . . . . . . . . . . . . . . . . . . . . . . .	a1n a2n . . . . amn	b1 b2 . . . . bn
zj
j=zj-cj

с₁,с₂,,...,с_n - коефіцієнти при змінних функції цілі;

a₁₁,a₁₂,...,a_mn - коефіцієнти при змінних системи обмежень;

b_i - вільні члени системи обмежень;

х_б - базисні змінні;

С_б - коефіцієнти функції цілі при базисних змінних.

Перші m рядків таблиці заповнюються за умовою, m+1 рядок обчислюється, за формулою: _j=z_j-c_j, де z_j- скалярний добуток елементів стовпчика С_б на відповідні елементи стовпців х_j, а c_j - коефіцієнти функції цілі, які записані у верхньому рядку таблиці.

Теорема 3 (ознака оптимальності) Опорний план ^=(х₁^, х₂^,..., х_к^,0,0,...,0) задачі лінійного програмування є оптимальним, якщо _j0 для всіх j (j=1,n).

Теорема 4 (умова необмеженості цільової функції) Якщо _к<0, а всі елементи к-го стовпчика не додатні, то цільова функція не обмежена зверху на допустимій множині.

У m+1 рядку стовпчика b_i знаходиться значення цільової функції, яке вона приймає на знайденому опорному плані.

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

• _j0 - вихідний опорний план оптимальний;

• _j<0 для деяких j, та всі відповідні цьому індексу величини a_ij0 (i=1,m) - цільова функція не обмежена зверху;

• _j<0 для деяких індексів j,та для кожного такого j хоча б одне з чисел a_ij додатне - перехід до нового опорного плану.

Цей перехід здійснюється виключенням із вихідного базису будь-якого вектора та введенням до нього нового.

Вектор, який включається до нового базису, відповідає тій оцінці _j, що не задовольняє умову оптимальності (для задачі максимізації - від’ємна, мінімізації - додатна). Якщо таких оцінок кілька, серед них вибирають найбільшу за абсолютною величиною і відповідну їй змінну вводять до базису. Припустимо, що індекс зазначеної змінної j=k. Відповідний стовпчик симплексної таблиці називають напрямним.

Для визначення змінної, що має бути виключена з базису, знаходять для всіх додатних a_ij напрямного стовпчика величини =b_i/a_ij. Вибирають найменше значення , яке вказує на змінну, що виводиться з базису. Припустимо, що це виконується для i=r. Відповідний рядок симплексної таблиці називатиметься напрямним.

Перетином напрямного стовпчика та напрямного рядка визначається число симплексної таблиці a_rk, яке називають розв’язуваним елементом. За допомогою елемента a_rk і методу Жордана-Гаусса розраховують нову симплексну таблицю.

Далі ітераційний процес повторюють доти, доки не буде визначено оптимальний план задачі.

У разі застосування симплекс-методу для розв’язування задач лінійного програмування можливі такі випадки:

• якщо в у рядку оцінок останньої симплекс-таблиці оцінка z_j-c_j=0 відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибравши розв’язуваний елемент у зазначеному стовпчику таблиці та здійснивши один крок симплекс-методом;

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

Алгоритм знаходження розв'язку задачі лінійного програмування симплекс методом /задача максимізації/:

1. Знаходять опорний план.

2. Складають симплекс-таблицю.

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

4. Знаходять напрямні строку та стовпець. Напрямний стов­пець визначається найбільшим за абсолютною величиною від'ємним числом j ,а напрямний рядок - найменшим з відношень компонент стовпця bi к додатнім ком­понентам напрямного стовпця.

5. Виконуючи перетворення за методом Жордана-Гаусса одержуємо новий опорний план.

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

Наприклад

Для виготовлення продукції використовують три види сировини. При цьому можна застосо­вувати чотири способи виробництва. Запаси си­ровини та кількість продукції, що виготовля­ється за 1 годину по кожному способу вироб­ництва наведені в таблиці:

	1	2	3	4	Запаси
1 2 3	1 1 1	2 1 3	1 2 3	0 1 2	18 30 40
	12	7	11	10	Випуск

Потрібно знайти план виробництва, при якому буде вироблятися максимум продукції.

Р о з в ’ я з а н н я:

Позначимо через x_j час застосування j способу ви­робництва, складемо математичну модель задачі:

Fmax=12x₁+7x₂+11x₃+10x₄

Зведемо цю задачу до канонічної форми:

Fmax=12x₁+7x₂+11x₃+10x₄+0x₅+0x₆+0x₇

Складемо симплекс-таблицю:

	12	7	11	10	0	0	0
Cb	x1	x2	x3	x4	x5	x6	x7	bi	хб
0 0 0	1 1 1	2 1 3	1 2 3	0 1 2	1 0 0	0 1 0	0 0 1	18 30 40	х5 х6 х7
										I
1=Z1-C1	-12	-7	-11	-10	0	0	0	0
12	1	2	1	0	1	0	0	18	х1
0	0	-1	1	1	-1	1	0	12	х6
0	0	1	2	2	-1	0	1	22	х7	II
Z2	12	24	12	0	12	0	0	216
2=Z2-C1	0	17	1	-10	12	0	0	216
12	1	2	1	0	1	0	0	18	х1
0	0	-3/2	0	0	-1/2	1	-1/2	1	х6
10	0	1/2	1	1	-1/2	0	1/2	11	х4	III
Z3	12	29	22	10	7	0	5	326
3=Z3-C1	0	22	11	0	7	0	5	326

1. Опорний план ₁(0;0;0;0;18;30;40) перевіряємо на оптимальність: обчислюємо значення ₁=Z₁-C₁ де Z₁ - скалярний добуток вектора Cb на вектор Aj(j=1,7), С₁ - коефіцієнти функції F. Серед значень ₁ є від'ємні, отже план ₁ не оптимальний. Необхідно перейти до іншого плану. Для цього вибираємо напрямний стовпець, що визначається оцінкою (-12) /обчислення простіші/, та напрямну строку /визначається найменшим з відношень елементів стовпця bi до відповідних елементів стовпця A1:18/1; 30/1; 40/1. Виконуючи перетворення за методом Жордана-Гаусса, одержуємо новий опорний план ₂(18;0;0;0;0;12;22).

2. Опорний план ₂ перевіряємо на оптимальність, виконую­чи аналогічні перетворення 1 етапу. Одержали новий опорний план ₃(18;0;0;11;0;1;0).

3. Повторюємо етапи перевірки плану ₃(18;0;0;11;0;1;0) на оптимальність, маємо невід’ємні значення ₃=Z₃-C₁, отже план ₃ оптимальний.

Відповідь: Fmax=326, *=(18;0;0;11).