Графічне розв’язання задачі лінійного програмування

Мета – опанувати ідею розв’язання задачі лінійного програмування та набути навиків розв’язування їх графічним методом

Розв’яжемо задачу графічним способом. Для цього в системі координат Х₁0Х₂ побудуємо рівняння прямих: x₁+x₂=3; x₁-x₂=3; -6x₁+4x₂=12; x₁=1, x₂=4. Відмітимо стрілками ті півплощини, які задовільняють кожній відповідній нерівності системи нерівностей стандартній формі запису задачі. Перетин півплощин - чотирикутник АBСD, який є областю допустимих розв’язків задачі. Далі будуємо вектор F(6,1) і перпендикулярно до нього пряму, яка проходить через точку (0,0). Пересуваємо цю пряму в напрямку вектора F до тих пір, поки вона не доторкнеться першої точки області допустимих значень. Це точка B.

Координати точки B знаходимо з рівнянь x₁+x₂=3 та x₁=1. Маємо x₁=1 x₂=2;. В цій точці функція F набуває свого найменшого значення 6*1+1*2+3=10.

Симплекс-метод

Мета – навчитися знаходити початковий опорний план, здійснювати перехід до іншого опорного плану та обчислювати оптимальний план задачі лінійного програмування за критерієм оптимальності

Розв’язання задачі здійснюється поетапно.

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

Запишемо систему обмежень у векторній формі:

де ─ - вимірний вектор-стовпець коефіцієнтів при (j=1,…,6) ─ - вимірний вектор-стовпець вільних членів системи

; ; ; ; ; ; .

Вектори A₄, A₅, A₆ - одиничні і лінійно-незалежні між собою вектори. Вони утворюють базис. Змінні x₄, x₅, x₆ називаються базисними, змінні x₁, x₂, x₃ ─ вільними і прирівнюються до нуля. У результаті отримуємо

або

Оскільки праворуч стоять всі невід’ємні коефіцієнти, а вектори A₄, A₅, A₆ ─ лінійно-незалежні одиничні, то отримаємо початковий опорний план:

_.

Етап 2. Складаємо симплекс-таблицю (табл.1) і перевіряємо цей план на оптимальність.

Таблиця 1

і	Базис	Сбаз	A0	C1=2	C2=-1	C3=3
				A1	A2	A3	A4	A5	A6
1	A4	0	8	3	0	-1	1	0	0
2	A5	0	6	2	1	-3	0	1	0
3	A6	0	1	─1	1	4	0	0	1
m+1				1=-2	2=1	3=3	4=0	5=0	6=0

Перший стовпець містить номер рядка (обмеження), другий – базисні вектори. Оскільки x₄, x₅, x₆ ─ базисні змінні, то відповідні їм вектори A₄, A₅, A₆ ─ базисні. Третій стовпець С_баз ─ коефіцієнти цільової функції при базисних векторах c₄=0, c₅=0, c₆=0. Стовпець A₀ ─ коефіцієнти опорного рішення. Оскільки x₄, x₅, x₆ дорівнюють правим частинам обмежень, то ці значення записуємо у стовпець A₀. В перший рядок табл.1 записуємо значення цільової функції c₁=2, c₂=-1, c₃=3, c₄=0, c₅=0, c₆=0

У стовпцях A₁, A₂, A₃, A₄, A₅, A₆ записуємо відповідні коефіцієнти в обмеженнях задачі при невідомих x₁, x₂, x₃, x₄, x₅, x₆.

У (m+1) рядку підраховуємо значення цільової функції на даному опорному плані. Значення дорівнює скалярному добутку вектора на вектор A₀:

Оцінки в (m+1) рядку обчислюються за формулою

тобто від скалярного добутку вектора на вектор віднімаємо значення коефіцієнта цільової функції . Так,

Зазначимо, що в (m+1) рядку базисним змінним завжди відповідають оцінки . Тому далі на відповідних позиціях можна ставити нулі.

Оскільки серед оцінок є від’ємні числа, то опорний план (0; 0; 0; 8; 6; 1) не є оптимальним і необхідно перейти до наступного опорного плану.

Етап 3. Для збільшення значення цільової функції (задача, яку розв’язуємо на максимум) серед оцінок треба вибрати найменшу – це . Стовпець A₃ тепер називаємо розв’язуваним (напрямним) і A₃ вводимо в базис.

Далі визначаємо розв’язуваний рядок. Для цього обчислюємо відношення компонент вектора A₀ до додатних компонент вектора, який вводимо в базис (A₃), і серед них обираємо найменше значення

Рядок, який відповідає мінімальному відношенню, називається розв’язувальним. Вектор A₆ виводимо з базису.

Елемент, що стоїть на перетині розв’язуваного рядка і розв’язуваного стовпця, називається розв’язуваним елементом.

Далі, використовуючи жорданові виключення, перераховуємо всі елементи таблиці. Знаходимо новий опорний план у новому базисі (табл. 2).

Таблиця 2

і	Базис	Сбаз	A0	C1=2	C2=-1	C3=3
				A1	A2	A3	A4	A5	A6
1	A4	0	8,25	2,75	0,25	0	1	0	0 ,25
2	A5	0	6,75	1,25	1	0	0	1	0,75
3	A3	3	0,25	-0,25	0,25	1	0	0	0,25
m+1			0,75	-2,75	1 ,75	0	0	0	0,75

У табл. 2 в стовпці “Базис” замість A₆ записуємо вектор A₃.

У стовпці проти A₃ записуємо значення коефіцієнта цільової функції с₃ = 3.

У стовпцях A₃, A₄, A₅, які відповідають базисним векторам, записуємо одиничні вектори. Підраховуємо елементи нової симплекс-таблиці.

Всі елементи розв’язуваного рядка (крім ) ділимо на розв’язуваний елемент. Інші елементи табл.2 перераховуємо за формулою жорданових виключень за правилом прямокутника.

Стовпці: , , ,

Далі обчислюємо коефіцієнти (m+1) рядка.

В табл.2 в рядку <0, і тому новий опорний план також не є оптимальним, його можна поліпшити за рахунок введення в базис вектора A₁. Тепер розв’язуваний стовпець - A₁.

Визначимо розв’язуваний рядок. Для цього обчислимо

Отже, 2,75 є розв’язуваним елементом, перший рядок ─ розв’язуваний, вектор A₄ слід вивести з базису.

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

Таблиця 3

і	Базис	Сбаз	A0	C1=2	C2=-1	C3=3
				A1	A2	A3	A4	A5	A6
1	A1	2	3	1	0,09091	0	0,36364	0	0,09091
2	A5	0	3	0	1,63636	0	-0,4545	1	0,63636
3	A3	3	1	0	0,27273	1	0,09091	0	0,27273
m+1			9	0	2	0	1	0	1

Оскільки всі оцінки , то отриманий опорний план є оптимальним. Максимальне значення цільової функції . Оскільки початкова задача була на мінімум цільової функції, то