денної форми навчання

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Запорізький національний технічний університет

МЕТОДИЧНІ ВКАЗІВКИ

До лабораторних робіт з дисципліни

«Математичні методи оптимізації та дослідження операцій»

для студентів спеціальності 7.080402

“Інформаційні технології проектування”

денної форми навчання

Методичні вказівки до лабораторних робіт з дисципліни «Математичні методи оптимізації та дослідження операцій» для студентів спеціальності 7.080402 “Інформаційні технології проектування” денної форми навчання / Укладачі: В.І. Дубровін, Л.Ю. Дейнега, Ю.С. Афонін. – Запоріжжя: ЗНТУ, 2006. – 57с.

Укладачі: В.І. Дубровін, Л. Ю. Дейнега,

Ю.С. Афонін

Рецензент: А.В. Притула

Відповідальний за випуск: В.І. Дубровін

Затверджено

на засіданні кафедри “Програмні засоби”

Протокол №2 від 24 жовтня 2006

ЗМІСТ

ВСТУП.. 5

1 Лабораторна робота № 1 ВИРІШЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ НА ОСНОВІ ЇЇ ГЕОМЕТРИЧНОЇ ІНТЕРПРЕТАЦІЇ. 6

1.1 Короткі теоретичні відомості 6

1.1.1 Застосування лінійного програмування. 6

1.1.2 Загальна і основна задача лінійного програмування. 9

1.1.3 Властивості основного задачі лінійного програмування. 13

1.1.4 Геометрична інтерпретація задачі лінійного програмування. 15

1.2 Завдання до лабораторної роботи. 23

1.3 Порядок виконання роботи. 26

1.4 Контрольні питання. 26

2 Лабораторна робота N2 ВИРІШЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ СИМПЛЕКСНИМ МЕТОДОМ 28

2.1 Короткі теоретичні відомості 28

2.1.1 Знаходження оптимального плану задачі лінійного програмування симплексним методом 28

2.1.2 Приклад рішення задачі лінійного програмування симплексним методом 34

2.2 Завдання до лабораторної роботи. 43

2.3 Домашнє завдання. 45

2.4 Порядок виконання роботи. 45

2.5 Зміст звіту. 46

2.6 Контрольні питання. 47

3 Лабораторна робота №3 Одномірний пошук оптимуму. Методи оптимізації з виключенням інтервалів 48

3.1 Короткі теоретичні відомості 48

3.2 Домашнє завдання. 48

3.3 Порядок виконання роботи. 49

3.4 Зміст звіту. 49

3.5 Контрольні питання. 49

4 Лабораторна робота №4 ПОЛІНОМІАЛЬНА АПРОКСИМАЦІЯ ТА МЕТОДИ ТОЧКОВОГО ОЦІНЮВАННЯ 51

4.1 Короткі теоретичні відомості 51

4.2 Домашнє завдання. 51

4.3 Порядок виконання роботи. 52

4.4 Зміст звіту. 52

4.5 Контрольні питання. 52

5 Лабораторна робота №5 МЕТОДИ ОПТИМІЗАЦІЇ З ВИКОРИСТАННЯМ ПОХІДНИХ 53

5.1 Короткі теоретичні відомості 53

5.2 Домашнє завдання. 53

5.3 Порядок виконання роботи. 53

5.4 Зміст звіту. 54

5.5 Контрольні питання. 54

6 Лабораторна робота № 6 ПОРІВНЯННЯ МЕТОДІВ ОДНОМІРНОГО ПОШУКУ 55

6.1 Короткі теоретичні відомості 55

6.2 Домашнє завдання. 56

6.3 Порядок виконання роботи. 56

6.4 Зміст звіту. 57

ПЕРЕЛІК ЛІТЕРАТУРИ.. 57

ВСТУП

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

Ефективність методів оптимізації, що дозволяють здійснити вибір найкращого варіанта без перевірки всіх можливих варіантів, тісно пов’язана з використанням тріади „модель-алгоритм-програма”.

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

Оскільки вимоги до задач оптимізації являються загальними та носять абстрактний характер, область використання методів оптимізації може бути доволі широкою. У зв’язку з цим в провідних університетах світу введені учбові дисципліни “Engineering Optimization” та “Operation Research”, які викладаються на рівні бакалаврата, а в деяких випадках – на рівні магістратури. Така тенденція спостерігається і в вузах України.

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

1 ЛАБОРАТОРНА РОБОТА № 1
ВИРІШЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ НА ОСНОВІ ЇЇ ГЕОМЕТРИЧНОЇ ІНТЕРПРЕТАЦІЇ

Мета роботи - вивчити методику рішення задач лінійного програмування на основі її геометричної інтерпретації; навчитися застосовувати лінійне програмування.

1.1 Короткі теоретичні відомості

1.1.1 Застосування лінійного програмування

Приклад 1.1. Для виготовлення деталей конструкційний матеріал може бути розкроєний декількома способами. Нехай при j-м варіанті розкрою (j=1, n) з 100 кв. м. конструкційного матеріалу виготовляється bij деталей i-го вигляду (i=1, m), а величина відходів при даному варіанті розкрою рівна Сj кв. м. Знаючи, що деталей i-го вигляду слід виготовити Вi штук, потрібно розкроїти матеріал так, щоб було отримано необхідну кількість деталей кожного виду при мінімальних загальних відходах. Скласти математичну модель задачі.

Для вирішення задачі припустимо, що по j-му варіанту розкроюється Сj сотень квадратних метрів матеріалу. Оскільки при розкрої 100 кв. м. матеріалу по j-му варіанту виходить bij деталей i-го виду, за всіма варіантами розкрою з використаних конструкційних матеріалів буде отримано

bi1*X1+bi2*X2+...+bin*Xn

деталей i-го виду. Оскільки повинно бути виготовлено Вi деталей даного виду, то

bi1*X1+bi2*X2+...+bin*Xn = Вi (i=1, m).

Загальна величина відходів за всіма варіантами розкрою матеріалу складе

F = C1*X1+C2*X2+...+Cn*Xn.

Таким чином, приходимо до наступної математичної задачі. Знайти мінімум функції

(1.1)

за умови, що її змінні задовольняють системі рівнянь

(i=1, m) (1.2)

і умові позитивності Хj > = 0 (j=1, n).

Сформульована задача є задачею лінійного програмування, оскільки функція (1.1) лінійна, а система (1.2) містить тільки лінійні рівняння.

Приклад 1.2. Конструктор має у своєму розпорядженні три види комплектів проводів A, B, C, що мають відповідно вартість C1, C2, C3. Кожен комплект містить алюмінієві і мідні дроти, причому в комплекті A міститься a11 - алюмінієвих, a21 - мідних; у комплекті B міститься a12 - алюмінієвих, a22 - мідних; у комплекті C міститься a13 - алюмінієвих, a23 - мідних проводів.

Відомо, що на монтаж установки витрачається алюмінієвих проводів не менше b1, а мідних - не менше b2.

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

Позначимо споживання кількості комплектів через X1, X2, X3. З урахуванням відомих вартостей комплектів цільова функція, що підлягає оптимізації, має вигляд

F = C1*X1+C2*X2+ C3*X3.

Складемо обмежувальні нерівности:

a11*X1 + a12*X2 +a13*X3 > = b1;

a21*X1 + a22*X2 +a23*X3 > = b2.

Перше рівняння описує потребу в алюмінієвих проводах, а друге - в мідних.

Потрібно знайти ненегативні значення елементів рішення, що мінімізують цільову функцію з урахуванням обмежень.

Приклад 1.3. Потрібно розробити апаратуру на основі серійних модулів (мікросхем) двох типів M1 і M2, що випускаються.

Відомо, що без урахування резервування в схемі апаратури повинно міститися модулів М1 не менше b1, а модулів М2 - не менше b2, крім того, відомо, що випускаються монтажні плати двох типів А і В, які передбачається використовувати як конструктивні несучі елементи для апаратури, що розробляється.

Відомо також, що в монтажному просторі плати А може розміститися a11 модулів М1 і a21 модулів М2. На монтажній платі В може бути розміщено a12 модулів М1 і a22 модулів М2.

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

З урахуванням умов і вимог задачі складемо цільову функцію F = C1*X1+C2*X2 ® min, де Х1 - кількість плат типу А, Х2 - кількість плат типу В.

Складемо обмежувальні рівняння:

a11*X1 + a12*X2 > = b1;

a21*X1 + a22*X2 > = b2

де Х1 і Х2 - цілі числа.

Перша нерівність описує розподіл модулів М1 серед плат А і В, а друга - розподіл серед тих же плат, але вже модулів М2.

1.1.2 Загальна і основна задача лінійного програмування

У попередньому підрозділі були розглянуті приклади завдань лінійного програмування (ЛП). У цих завданнях потрібно було знайти максимум або мінімум лінійної функції за умови, що її змінні приймали ненегативні значення і задовольняли деякій системі лінійних рівнянь або лінійних нерівностей. Кожне з цих завдань є окремим випадком загальної задачі лінійного програмування.

Визначення 1.1. Загальною задачею лінійного програмування називається задача, яка полягає у визначенні максимального (мінімального) значення функції

(1.3)

за умов

(i=1, k); (1.4)

(i=k+1, m); (1.5)

Xj 0 (i=1, L; L< =n) (1.6)

де aij, bi, cj - задані постійні величини і k< =m.

Визначення 1.2. Функція (1.3.) називається цільовою функцією (або лінійною формою) задачі (1.3) - (1.6), а умови (1.4) - (1.6) - обмеженнями даної задачі.

Визначення 1.3. Стандартною (або симетричною) задачею лінійного програмування називається задача, яка полягає у визначенні максимального значення функції (1.3) при виконанні умов (1.4) і (1.6), де k=m і L=n.

Визначення 1.4. Основною (або канонічною) задачею лінійного програмування називається задача, яка полягає у визначенні максимального значення функції (1.3) при виконанні умов (1.5) і (1.6), де k=0 і L=n.

Визначення 1.5. Сукупність чисел X=(X1, X2...Xn), що задовольняють обмеженням (1.5) - (1.6), називається допустимим рішенням (або планом).

Визначення 1.6. План X*=(X1*, X2*..., Xn*), при якому цільова функція задачі (1.3) приймає максимальне (мінімальне) значення, називається оптимальним.

Значення цільової функції (1.3) при плані Х позначатимемо через F(X). Отже, Х* - оптимальний план задачі, якщо для будь-якого Х виконується нерівність

F(X) < = F(X*)

/відповідно F(X) > = F(X*)/.

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

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

У тому випадку, коли потрібно знайти мінімум функції

F = C1*X1+C2*X2+...+Сn*Xn, можна перейти до знаходження максимуму функції F1 = -F = -C1*X1 - C2*X2 -... -Сn*Xn, оскільки min F = max (-F).

Обмеження-нерівність початкової задачі ЛП, що має вид " < =", можна перетворити в обмеження-рівність додаванням до його лівої частини додаткової ненегативної змінної, а обмеження-нерівність виду " > =" - в обмеження-рівність відніманням з його лівої частини додаткової ненегативної змінної.

Таким чином, обмеження-нерівність

ai1*X1 + ai2*X2 +...+ ain*Xn < = bi

перетвориться в обмеження-рівність

ai1*X1 + ai2*X2 +...+ ain*Xn + Xn+i = bi (Xn+i > = 0) (1.7)

а обмеження-нерівність

ai1*X1 + ai2*X2 +...+ ain*Xn > = bi

у обмеження-рівність

ai1*X1 + ai2*X2 +...+ ain*Xn - Xn+i = bi (Xn+i > = 0). (1.8)

В той же час кожне рівняння системи обмежень

ai1*X1 + ai2*X2 +...+ ain*Xn = bi

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

ai1*X1 + ai2*X2 +...+ ain*Xn < = bi; (1.9)

ai1*X1 - ai2*X2 -...- ain*Xn < = -bi.

Число ненегативних змінних, що вводяться, при перетворенні обмежень-нерівностей в обмеження-рівність рівне числу перетворюваних нерівностей.

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

Відзначимо, нарешті, що якщо змінна Хk не підпорядкована умові позитивності, то її слід замінити двома ненегативними змінними Uk і Vk, прийнявши

Xk = Uk - Vk.

Приклад 1.4. Записати у формі основної задачі лінійногопрограмування наступну задачу. Знайти максимум функції

F = 3*X1-2*X2-5*X4+X5

за умов

2*Х1+Х3 - Х4+Х5 < = 2;

Х1-X3+2*Х4+Х5 < = 3;

2*Х2+Х3-Х4+2*X5 < = 6;

Х1 + Х4-5*Х5 > = 8

X1, X2, X3, X4, X5 > =0

У даному завданні потрібно знайти максимум функції, а система обмежень містить чотири нерівності. Отже, щоб записати її у формі основної задачі, потрібно перейти від обмежень-нерівностей до обмежень-рівностей. Оскільки число нерівностей, що входять в систему обмежень задачі, рівне чотирьом, то цей перехід може бути здійснений введенням чотирьох додаткових ненегативних змінних. При цьому до лівих частин кожної з нерівностей виду " < =" відповідна додаткова змінна додається, а з лівих частин кожної з нерівностей виду " > =" віднімається. В результаті, обмеження приймають вигляд

2*Х1+Х3 - Х4+Х5+Х6 = 2;

Х1-X3+2*Х4+Х5+Х7 = 3;

2*Х2+Х3-Х4+2*X5+Х8 = 6;

Х1 + Х4-5*Х5-Х9 = 8

X1, X2..., Х9 > =0.

Отже, дана задача може бути записана у формі основної задачі таким чином: максимізувати функцію F = 3*X1-2*X2-5*X4+X5 за умов

2*Х1+Х3 - Х4+Х5+Х6 = 2;

Х1-X3+2*Х4+Х5+Х7 = 3;

2*Х2+Х3-Х4+2*X5+Х8 = 6;

Х1 + Х4-5*Х5-Х9 = 8

X1, X2..., Х9 > =0.

Приклад 1.5. Записати задачу, що полягає в мінімізації функції F = -X1+2*X2-X3+X4 за умов

2*Х1 - Х2 - Х3 + Х4 < = 6;

Х1+2*X2 + Х3 - Х4 > = 8;

3*Х1 - Х2+2*Х3+2*X4< = 10;

-Х1+3*Х2+5*Х3-3*Х4 = 15

X1, X2..., Х4 > =0

у формі основного задачі ЛП.

У даному завданні потрібно знайти мінімум цільової функції, а система обмежень містить три нерівності.

Отже, щоб записати її у формі основної задачі, замість знаходження мінімуму функції F потрібно знайти мінімум функції F1 = -F при обмеженнях, що виходять з обмежень початкової задачі додаванням до лівих частин кожного з обмежень нерівностей виду " < =" додаткової ненегативної змінної і відніманням з лівих частин кожного з обмежень нерівностей виду " > =".

Отже, початкова задача може бути записана у формі основної задачі ЛП так: знайти максимум функції

F1 = X1-2*X2+X3-X4 за умов

2*Х1 - Х2 - Х3 + Х4+Х5 = 6;

Х1+2*X2 + Х3 - Х4-Х6 = 8;

3*Х1 - Х2+2*Х3+2*X4+Х7 = 10;

-Х1+3*Х2+5*Х3-3*Х4 = 15

X1, X2..., Х7 > =0.

1.1.3 Властивості основного задачі лінійного програмування

Розглянемо основну задачу ЛП. Як було відмічено в підрозділі 1.1.2, вона полягає у визначенні максимального значення функції

за умов

= Bj (i=1, m), Xj> =0 (j=1, n).

Перепишемо цю задачу у векторній формі. Знайти максимум функції

F = C*X (1.10)

за умов

X1*Р1+X2*Р2+...+Xn*Рn = Р0; (1.11)

X > = 0 (1.12)

де З = (C1, C1..., Cn); X = (X1, X2..., Xn); C*X - скалярний добуток; Р1,..., Рn і Р0 - m-мірні вектори-стовпці, складені з коефіцієнтів при невідомих і вільних членах системи рівнянь задачі:

b1 a11 a12 a1n

b2 a21 a22 a2n

Р0 =.; Р1 =.; Р2 =.;...; Рn =.

....

....

bn am1 am2 amn

Визначення 1.6. План X = (X1, X2..., Xn) називається опорним

планом основної задачі лінійного програмування, якщо система векторів Рj, що входять в розкладання (1.11) з позитивними коефіцієнтами Xj, лінійно незалежна.

Оскільки вектори Рj є m-мірними, то з визначення опорного плану виходить, що число його позитивних компонент не може бути більше, ніж m.

Визначення 1.7. Опорний план називається невиродженим, якщо він містить рівно m позитивних компонент, інакше він називається виродженим.

Властивості основної задачі ЛП (1.10) -(1.12) тісним чином

пов'язані з властивостями опуклих множин.

Визначення 1.8. Нехай X1, X2..., Xn - довільні точки

евклідового простору En. Опуклою лінійною комбінацією цих точок називається сума 1*X1+ 2*X2+...+ n*Xn, де i - довільні ненегативні числа, сума яких рівна 1.

; a> =0 (i=1, n).

Визначення 1.9. Множина називається опуклою, якщо

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

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

Теорема 1.1. Безліч планів основної задачі лінійного

програмування є опуклою (якщо воноа не порожня).

Визначення 1.11. Непорожня безліч планів основної задачі лінійного програмування називається багатогранником рішень, а всяка кутова точка багатогранника рішень - вершиною.

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

Теорема 1.3. Якщо система векторів Р1, Р2..., Рk (k< =n) у

розкладанні (1.11) лінійно-незалежна і така, що

X1*Р1+X2*Р2+...+Xk*Рk = Р0 (1.13)

де все Xj> =0, то крапка X = (X1, X2..., Xk, 0,..., 0) є

вершиною багатогранника рішень.

Теорема 1.4. Якщо X = (X1, X2..., Xn) - вершина багатогранника рішень, то вектори Рj, відповідні позитивним Xj в розкладанні (1.11), лінійно-незалежні.

1.1.4 Геометрична інтерпретація задачі лінійного програмування

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

Вершину багатогранника рішень, в якій цільова функція приймає максимальне значення, знайти порівняно просто, якщо задача, записана в стандартній формі, містить не більше двох змінних, тобто n-r < = 2, де n - число змінних; r - ранг матриці, складеної з коефіцієнтів в системі обмежень задачі.

Знайдемо рішення задачі, що полягає у визначенні максимального значення функції

F = C1*X1 + C2*X2 (1.14)

за умов

ai1*X1+ai2*X2 < = bi (i=1, k) (1.15)

Xj > = 0 (j=1, 2) (1.16)

Кожна з нерівностей (1.15), (1.16) системи обмежень визначає напівплощина відповідно з граничними прямими

ai1*X1+ai2*X2 = bi; (i=1, k); X1=0 і X2=0.

В тому випадку, якщо система нерівностей сумісна, область її рішень є безліч точок, що належать всім вказаним напівплощинам. Оскільки безліч точок перетину даних напівплощин - опукла, то областю допустимих рішень задачі (1.14) - (1.16) є опукла безліч точок, яка називається багатокутником рішень (введений раніше термін " багатогранник рішень" зазвичай уживається, якщо n> =3). Сторони цього багатокутника лежать на прямих, рівняння яких виходять з початкової системи обмежень заміною знаків нерівностей на знаки точної рівності.

Таким чином, початкова задача ЛП полягає в знаходженні такої точки багатокутника рішень, в якій цільова функція F приймає максимальне значення. Ця точка існує тоді, коли багатокутник рішень не порожній і на ньому цільова функція обмежена зверху.

За вказаних умов в одній з вершин багатокутника рішень цільова функція приймає максимальне значення. Для визначення даної вершини побудуємо лінію рівня C1*X1+C2*X2 = h

(де h - деяка постійна), що проходить через багатокутник рішень і пересуватимемо її у напрямі вектора С=(C1, C2) до тих пір, поки вона не пройде через останню її загальну точку з багатокутником рішень. Координати вказаної точки і визначають оптимальний план даної задачі.

Закінчуючи розгляд геометричної інтерпретації задачі (1.14) - (1.16), відзначимо, що при знаходженні її рішення можуть зустрітися випадки, зображені на рис.1.1. - 1.4. Рис.1.1. характеризує такий випадок, коли цільова функція приймає максимальне значення в єдиній точці А. З рис.1.2. видно, що максимальне значення цільова функція приймає в будь-якій точці відрізка АВ. На рис.1.3. зображений випадок, коли цільова функція не обмежена зверху на безлічі допустимих рішень, а на рис.1.4. - випадок, коли система обмежень задачі несумісна.

Відзначимо, що знаходження мінімального значення лінійної функції при даній системі обмежень відрізняється від знаходження її мінімального значення при тих же обмеженнях лише тим, що лінія рівня C1*X1+C2*X2 = h пересувається не у напрямі вектора C=(C1, C2), а в протилежному напрямі. Таким чином, відмічені вище випадки, що зустрічаються при знаходженні максимального значення цільової функції, мають місце і при знаходженні її мінімального значення.

Отже, знаходження рішення задачі ЛП (1.14) - (1.16) на основі її геометричної інтерпретації включає наступні етапи.

1. Будують прямі, рівняння яких виходять в результаті

заміни в обмеженнях (1.15) і (1.16) знаків нерівностей на знаки точної рівності.

2. Знаходять напівплощини, які визначаються кожним з обмежень задачі.

3. Знаходять багатокутник рішень.

4. Будують вектор C=(C1, C2).

5. Будують пряму C1*X1+C2*X2 = h, що проходить через багатокутник рішень.

6. Пересувають пряму C1*X1+C2*X2 = h у напрямі вектора С, внаслідок чого знаходять точку (точки), в яких цільова функція приймає максимальне значення, або встановлюють необмеженість зверху функції на безлічі планів.

7.Визначають координати точки максимуму функції і обчислюється значення цільової функції в цій точці.

Приклад 1.6. Для виробництва двох видів виробів А і В

підприємство використовує три види комплектуючих. Норми витрат комлектуючих кожного виду на виготовлення одиниці продукції даного вигляду приведені в табл.1.1.

Таблиця 1.1

У табл.1.1. вказані також прибуток від реалізації одного

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

Враховуючи, що вироби А і В можуть вироблятися в будь-яких країнах, потрібно скласти такий план їх випуску, при якому прибуток підприємства від реалізації всіх виробів виявиться максимальним.

Припустимо, що підприємство виготовить Х1 виробів виду А і Х2 виробів виду В. Оскільки виробництво продукції обмежене комплектуючими кожного виду, що є у розпорядженні підприємства і кількість виробів, що виготовляються, не може бути негативною, повинні виконуватися нерівності

12*Х1 + 4*Х2 < = 300;

4*Х1 + 4*X2 < = 120;

3*Х1 + 12*Х2 < = 252

X1, X2 > = 0.

Загальний прибуток від реалізації Х1 виробів виду А і Х2 виробів виду В складе F = 30*X1 + 40*X2.

Таким чином, ми приходимо до наступної математичної задачі. Серед всіх ненегативних рішень даної системи лінійних нерівностей потрібно знайти таке, при якому функція F приймає максимальне значення.

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

12*Х1 + 4*Х2 = 300 (I)

4*Х1 + 4*X2 = 120 (II)

3*Х1 + 12*Х2 = 252 (III)

X1 = 0 (IV)

X2 = 0. (V).

Ці прямі зображені на рис.1.5. Кожна з побудованих прямих ділить площину на дві напівплощини. Координати точок однієї напівплощини задовольняють початковій нерівності, а інший - ні. Щоб визначити шукану напівплощину, потрібно узяти яку-небудь точку що належить одній з напівплощин, і перевірити, чи задовольняють її координати даній нерівності.

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

Знайдемо, наприклад, напівплощину, яка визначена нерівністю 12*Х1 + 4*Х2 < 300 (на рис.1.5. це пряма I), візьмемо яку-небудь точку, що належить одній з напівплощин, наприклад, початок координат - точку (0; 0). Координати цієї точки задовольняють нерівності 12*0 + 4*0 < 300; таким чином, напівплощина якій належить точка (0; 0), визначається нерівністю

12*Х1+4*Х2 < = 300. Це і показано стрілками на рис.1.5.

Перетин отриманих напівплощин і визначає багатокутник рішень даної задачі.

Як видно з рис.1.5, багатокутником рішень є п'ятикутник OABCD. Координати будь-якої точки, що належить цьому п'ятикутнику, задовольняють даній системі нерівностей і умові позитивності змінних. Тому, сформульована задача буде вирішена, якщо ми зможемо знайти точку, що належить п'ятикутнику OABCD, в якій функція F приймає максимальне значення.

Щоб знайти вказану точку, побудуємо вектор С = (30; 40) і пряму 30*Х1 + 40*Х2 = h, де h - деяка постійна, при якій пряма 30*Х1 + 40*Х2 = h має загальні точки з багатокутником рішень. Покладемо, наприклад, h = 480 і побудуємо пряму 30*Х1 + 40*Х2 = 480 (рис.1.5.).

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

Переміщаючи побудовану пряму 30*Х1 + 40*Х2 = 480 у напрямі вектора С, бачимо, що останньою загальною точкою її з багатокутником рішень задачі служить точка В. Координати цієї точки і визначають план випуску виробів А і В, при якому прибуток від їх реалізації є максимальним.

Знайдемо координати точки В як точки перетину прямих II і III. Отже, її координати задовольняють рівнянням цих прямих

4*Х1 + 4*X2 = 120

3*Х1 + 12*Х2 = 252.

Вирішивши цю систему рівнянь, отримаємо Х1'=12, X2'=18. Отже, якщо підприємство виготовить 12 виробів виду А і 18 виробів виду В, то воно отримає максимальний прибуток, Fmax = 30*12 + 40*18 = 1080 грн.

1.2 Завдання до лабораторної роботи

Використовуючи геометричну інтерпретацію, знайти рішення (або переконатися в нерозв'язності) задачі ЛП.

1. F=7*X1+6*X2 ® max; 2. F=3*X1-2*X2 max;

2*X1+5*X2 > = 10, 2*X1+X2 < = 11

5*X1+2*X2 > = 10 -3*X1+2*X2 < = 10

X1 < = 6, 3*X1+4*X2 > = 20;

X2 < = 5; X1, X2 > =0.

X1, X2 > =0.

3. F=5*X1-3*X2 ® min; 4. F=X1+X2 ® max;

3*X1+2*X2 > = 6, 2*X1+X2 < = 14

2*X1-3*X2 > = -6, -3*X1+2*X2 < = 9

X1-X2 < = 4, 3*X1+4*X2 > = 27;

4*X1+7*X2 < = 28; X1, X2 > =0.

X1, X2 > =0.

5. F=7*X1-2*X2 ® max; 6. F=2*X1+2*X2 ® max;

5*X1-2*X2 < = 3, X1-2*X2 > = 4

X1+X2 > = 1, 5*X1+2*X2 > = 10

-3*X1+X2 < = 3, 4*X1-3*X2 < = 12

2*X1+X2 < = 4; 7*X1+4*X2 < = 28;

X1, X2 > =0. X1, X2 > =0.

7. F=2*X1+2*X2 ® max; 8. F=2*X1-4*X2 ® max;

3*X1-2*X2 > = -6, 8*X1-5*X2 < = 16

X1+X2 > = 3, X1+3*X2 < = 2

X1 < = 3, 2*X1+7*X2 > = 9;

X2 < = 5; X1, X2 > =0.

X1, X2 > =0.

9. F=X1+2*X2 ® max; 10. F=3*X1+3*X2 ® max;

5*X1-2*X2 < = 4, X1-4*X2 < = 4

X1-2*X2 > = -4, 3*X1+2*X2 < = 6

X1+X2 > = 4; -X1+X2 < = 1

X1, X2 > =0. X1+2*X2 > = 2;

X1, X2 > =0.

11. F=2*X1-X2 ® max; 12. F=5*X1+X2 ® min;

X1-X2 > = -3, X1+7*X2 > = 7

6*X1+7*X2 < = 42 -2*X1+X2 < = 6

2*X1-3*X2 < = 6, 2*X1+5*X2 > = 10

X1+X2 > = 4; 5*X1+2*X2 > = 10

X1, X2 > =0. 7*X1+7*X2 > = 7

X1 < = 6

X2 < = 7;

X1, X2 > =0.

13. F=X1-X2 ® max; 14. F=7*X1+X2 ® max;

-X1+X2 > = 8, X1+X2 < = 14

8*X1+5*X2 < = 80, 3*X1-5*X2 < = 15

X1-2*X2 < = 2, 5*X1+3*X2 > = 21;

X1+4*X2 > = 4; X1, X2 > =0.

X1, X2 > =0.

15. F=7*X1-X2 ® min; 16. F=X1+X2 ® min;

X1+X2 > = 3, 3*X1+X2 > = 8

5*X1+X2 > = 5, X1+2*X2 > = 6

X1+5*X2 < = 5; X1-X2 < = 3;

0 < = X1 < = 4; X1, X2 > =0.

0 < = X2 > = 4.

17. F=X1+3*X2 ® max; 18. F=2*X1+X2 ® max;

-X1+X2 < = 3, X1-X2 > = 4

4*X1+3*X2 < = 20; X1+X2 > = 10

X1, X2 > =0. 4*X1-X2 < = 12

7*X1+X2 < = 7;

X1, X2 > =0.

19. F=2*X1+2*X2 ® max; 20. F=2*X1-4*X2 ® max;

3*X1-2*X2 > = -6, 8*X1-5*X2 < = 16

X1+X2 > = 3, X1+3*X2 > = 2

X1 < = 3, 2*X1+7*X2 < = 9;

X2 < = 5; X1, X2 > =0.

X1, X2 > =0.

21. F=3*X1+2*X2 ® max; 22. F=X1+X2 ® max;

3*X1+X2 < = 21, X1+2*X2 < = 14

2*X1+3*X2 < = 30 -5*X1+3*X2 < = 15

2*X1 < = 16; 4*X1+6*X2 > = 24;

X1, X2 > =0. X1, X2 > =0.

23. F=X1+2*X2 ® max; 24. F=-2*X1+X2 ® min;

4*X1-2*X2 < = 12, 3*X1-2*X2 < = 12

-X1+3*X2 < = 6 -X1+2*X2 < = 8

2*X1+4*X2 > = 16; 2*X1+3*X2 > = 6;

X1, X2 > =0. X1, X2 > =0.

25. F=2*X1+3*X2 ® min; 26. F=X1+2*X2 ® max;

2*X1+X2 > = 8, X1+X2 < = 6

X1+2*X2 > = 6; *X1+10*X2 < = 26

X1, X2 > =0. X1+11*X2 < = 20;

X1, X2 > =0.

1.3 Порядок виконання роботи

1. Вивчити приведені в підрозд.1.1. теоретичні відомості про лінійне програмування (ЛП), звернувши особливу увагу на розглянуті приклади застосування ЛП (Приклади 1.1-1.6).

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

3. Знайти напівплощини, які визначені кожним з обмежень задачі.

4. Визначити багатокутник рішень даної задачі (якщо обмеження задачі сумісні).

5. Побудувати вектор С= (С1, С2), де С2, С2 - константи при невідомих цільовій функції задачі ЛП.

6. Побудувати пряму С1*Х1 + С2*Х2 = h, де h - деяка постійна, при якій вказана пряма має загальні точки з багатокутником рішень.

7. Переміщаючи побудовану пряму у напрямі вектора С, знайти точку (точки), в якій цільова функція приймає максимальне значення.

8. Визначити координати точки максимуму цільової функції і обчислити значення цільової функції в цій точці.

9. Етапи рішення задачі ЛП на основі її геометричної інтерпретації оформити аналогічно рішенню прикладу 1.6. Привести малюнок, аналогічний рис.1.5.

1.4 Контрольні питання

1. Приведіть приклад використання ЛП. Складіть математичну модель задачі.

2. Сформулюйте загальну задачі ЛП.

3. Дайте визначення стандартної (симетричної) і основної (канонічної) задачі ЛП.

4. Що називається допустимими і оптимальним рішеннями задачі ЛП? Дайте геометричну інтерпретацію.

5. Як визначити кількість додаткових ненегативних змінних, які слід вводити при переході від обмежень-нерівностей задачі ЛП до обмежень-рівності. Який їх сенс?

6. Як можна звести задачі мінімізації цільової функції до задачі максимізації?

7. Яким чином замінюються змінні, що не підкоряються умові позитивності?

8. Як підготувати і вирішити задачу ЛП на основі її геометричної інтерпретації?

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

2 Лабораторна робота N2
ВИРІШЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ СИМПЛЕКСНИМ МЕТОДОМ

Мета роботи - вивчити методику вирішення задачі лінійного програмування симплексним методом.

2.1 Короткі теоретичні відомості

2.1.1 Знаходження оптимального плану задачі лінійного програмування симплексним методом

Вирішення задачі лінійного програмування можна знайти симплексним методом. Перш ніж застосовувати цей метод, слід записати початкову задачу у формі основної задачі ЛП, якщо вона не має такої форми запису.

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

Вказаний перехід можливий, якщо відомий який-небудь початковий опорний план. Розглянемо задачу, для якої цей план можна безпосередньо записати.

Нехай потрібно знайти максимальне значення функції

F = C1*X1+C2*X2+...+Cn*Xn

за умов

X1 + A1m+i*Xm+i +... + A1n*Xn = B1

X2 + A2m+i*Xm+i +... + A2n*Xn = B2

..................

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

Нехай

(j=0, n).

Покладемо

(j=1, n); j = Zj - Cj (j=1, n).

Оскільки вектори Р1, Р2..., Рm - одиничні, то

Xij = Aij і Zj = , а

j = .

Теорема 2.1. (ознака оптимальності опорного плану).

Опорний план Х'=(X1'; X2';...; Xm'; 0; 0;...; 0) задачі є оптимальним, якщо j> =0 для будь-якого j (j=1, n).

Теорема 2.2. Якщо к< 0 для деякого j=к і серед чисел Aiк

(i=1, m) немає позитивних (Aiк< =0), то цільова функція задачі не обмежена на безлічі її планів.

Теорема 2.3. Якщо опорний план Х задачі невироджений і к< 0, але серед чисел Aiк є позитивні (не всі Aiк< =0), то існує опорний план Х' такий, що F(X')> F(X).

Сформульовані теореми дозволяють перевірити, чи є знайдений опорний план оптимальним і виявити доцільність переходу до нового опорного плану.

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

Таблиця 2.1

У стовпці Сб цієї таблиці записують коефіцієнти при невідомих цільової функції, що мають ті ж індекси, що і вектори даного базису.

У стовпці Ро записують позитивні компоненти початкового опорного плану, у ньому ж в результаті обчислень отримують позитивні компоненти опорного плану. Стовпці векторів Рj являють собою коефіцієнти розкладання цих векторів за векторами даного базису.

У табл.2.1. перші m рядків визначаються початковими даними задачі, а показники (m+1) -го рядка обчислюють.

У цьому рядку в стовпці вектора Ро записують значення цільової функції, яке вона приймає при даному опорному плані, а в стовпці вектора Рj - значення j = Zj - Cj.

Значення Zj знаходиться як скалярний добуток вектора Рj (j=1, n) на вектор Сб = (C1, C2..., Cm):

Zj = , (j=1, n).

Значення Fo рівне скалярному добутку вектора Рo на вектор Сб:

Fo = .

Після заповнення табл.2.1. початковий опорний план

перевіряють на оптимальність. Для цього проглядають елементи (m+1) -го рядка таблиці. В результаті може мати місце один з наступних трьох випадків:

а) Dj> =0 для j=m+1, m+2..., n (при j=1, m Zj=Cj і, відповідно, j=0). Тому в даному випадку числа j> =0 для всіх j від 1 до n;

б) Dj< 0 для деякого j та всі відповідні цьому індексу величини Aij< =0 (i=1, m);

в) Dj< 0 для деяких індексів j та для кожного такого j хоча б одне з чисел Aij позитивне.

У першому випадку на підставі ознаки оптимальності початковий опорний план є оптимальним. У другому випадку цільова функція не обмежена зверху на безлічі планів, а в третьому випадку можна перейти від початкового плану до нового опорного плану, при якому значення цільової функції збільшиться. Цей перехід від одного опорного плану до іншого здійснюється виключенням з початкового базису якого-небудь з векторів і введенням в нього нового вектору. Як вектор, що вводиться в базис, можна узяти будь-який з векторів Рj, що має індекс j, для якого Dj< 0. Нехай, наприклад, Dк< 0 і вирішено ввести в базис вектор Рк. Для визначення вектора, який підлягає виключенню з базису, знаходять min (Bi/Aiк) для всіх Aiк> 0. Хай цей мінімум досягається при i = r. Тоді з базису виключають вектор Рr, а число Arк називають розв’язуючим елементом. Стовпець і рядок, на перетині яких знаходиться розв’язуючий елемент, називають направляючим.

Після виділення розв’язуючого рядка і розв’язуючого стовпця знаходять новий опорний план Х і коефіцієнти розкладання векторів Рj через вектори нового базису, відповідні новому опорному плану. Позитивні компоненти нового опорного плану обчислюють по формулам

Bi-(Br/Arк)*Aiк при i< > r,

Bi' = (2.1)

Br/Arк при i=r,

Коефіцієнти розкладання векторів Рj через вектори нового базису, що відповідають новому опорному плану, по формулам

Aij-(Arj/Arк)*Aiк при i< > r;

Aij' = (2.2)

Arj/Arк при i=r.

Після обчислення Вi' і A'ij згідно (2.1) і (2.2) їх значення заносять в табл.2.2.

Таблиця 2.2

Елементи (m+1) -го рядка цієї таблиці можуть бути обчислені або по формулам

Fo' = Fo - (Br/Arк)*Dk; (2.3)

Dj' = Dj - (Arj/Arк)* Dk (2.4)

або на підставі їх визначення.

Наявність двох способів знаходження елементів (m+1) -го рядка дозволяє здійснювати контроль правильності обчислень, що проводяться.

З (2.3) витікає, що при переході від одного опорного плану до іншого найдоцільніше ввести в базис вектор Рj, що має індекс j, при якому максимальним по абсолютній величині є число (Br/Arj)* j (j> 0, Arj> 0). Проте в цілях спрощення обчислювального процесу надалі будемо вектор, що вводиться в базис, визначати, виходячи з максимальної абсолютної величини негативних чисел j. Якщо ж таких чисел декілька, то в базис вводитимемо вектор, що має такий же індекс, як і максимальне з чисел Cj, що визначаються даними числами j (j< 0).

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

У стовпцях векторів, що входять в базис, на перетині рядків і стовпців однойменних векторів проставляють одиниці, а решта всіх елементів даних стовпців покладають рівними нулю.

Елементи векторів Рo і Рj в рядку нової симплекс-таблиці, в якій записаний вектор, що вводиться в базис, отримують з елементів цього ж рядка початкової таблиці діленням їх на величину розв’язуючого елементу. У стовпці Сб в рядку вектора, що вводиться, проставляють величину Ск, де к - індекс вектора, що вводиться.

Решта елементів стовпців векторів Рo і Рj новою

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

1. Число, що стоїть в початковій симплекс-таблиці на місці шуканого елементу нової симплекс-таблиці.

2. Число, що стоїть в початковій симплекс-таблиці на перетині рядка, в якому знаходиться шуканий елемент нової

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

3. Число, що стоїть в новій симплекс-таблиці на перетині

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

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

Після заповнення нової симплекс-таблиці переглядають елементи (m+1) -го рядка. Якщо всі Z'j-Cj> =0, то новий опорний план є оптимальним. Якщо ж серед вказаних чисел є негативні, то, використовуючи описану вище послідовність дій, знаходять новий опорний план. Цей процес продовжують до тих пір, поки або не отримують оптимальний план задачі, або не встановлюють її нерозв'язність.

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

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

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

2.1.2 Приклад вирішення задачі лінійного програмування симплексним методом

Для виготовлення різних виробів А, В і С підприємство використовує три різні види сировини. Норми витрати сировини на виробництво виробів кожного виду, ціна одного виробу А, В і С, а також загальна кількість сировини кожного виду, яка може бути використане підприємством, приведені в табл.2.3.

Таблиця 2.3

Вироби А, В і С можуть проводитися в будь-яких співвідношеннях (збут забезпечений), але виробництво обмежене виділеною підприємству сировиною кожного виду.

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

Складемо математичну модель задачі. Шуканий випуск виробів А позначимо через Х1, виробів В - через Х2, виробів С - через Х3. Оскільки є обмеження на виділений підприємству фонд сировини кожного виду, змінні Х1, Х2, Х3 повинні задовольняти наступній системі нерівностей:

18*Х1+15*Х2+12*Х3 < = 360;

6*Х1+4*Х2+8*Х3 < = 192; (2.5)

5*Х1+3*Х2+3*Х3 < = 180.

Загальна вартість проведеної підприємством продукції за умови випуску Х1 виробів А, Х2 виробів В і Х3 виробів С складає

F = 9*X1 + 10*X2 + 16*X3. (2.6)

За своїм змістом змінні Х1, Х2, Х3 можуть приймати тільки ненегативні значення

Х1, Х2, Х3 > = 0. (2.7)

Таким чином, приходимо до наступного математичного задачі: серед всіх ненегативних рішень системи нерівностей (2.5) потрібно знайти таке, при якому функція (2.6) приймає максимальне значення.

Запишемо цю задачу у формі основної задачі ЛП. Для цього перейдемо від обмежень-нерівностей до обмежень-рівностей.

Введемо три додаткові змінні, внаслідок чого обмеження запишуться у вигляді системи рівнянь

18*Х1+15*Х2+12*Х3+Х4 = 360;

6*Х1+4*Х2+8*Х3+Х5 = 192;

5*Х1+3*Х2+3*Х3+Х6 = 180.

Введені додаткові змінні означають не використовувану при даному плані виробництва кількість сировини того або іншого виду. Наприклад, Х4 - це невживана кількість сировини I виду.

Перетворену систему рівнянь запишемо у векторній формі:

X1*Р1 + X2*Р2 + X3*Р3 + X4*Р4 + X5*Р5 + X6*Р6 = Р0,

де

18 15 12 1

Р1 = 6; Р2 = 4; Р3 = 8; Р4 = 0;

5 3 3 0

0 0 360

Р5 = 1; Р6 = 0; Р0 = 192.

0 1 180

Оскільки серед векторів Р1, Р2, Р3 є три одиничні вектори (нагадаємо, що одиничним називається вектор, модуль якого рівний одиниці), для даного задачі можна безпосередньо записати опорний пл