Методичні вказівки

1 2

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

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

ОДНОВИМІРНІ МЕТОДИ ОПТИМІЗАЦІЇ

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

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

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

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

“Програмне забезпечення автоматизованих систем”

напряму 6.050103 “Програмна інженерія”

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

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

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

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

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

Затверджено

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

Протокол №1 від 28.08.2008

ЗМІСТ

ВСТУП.. 5

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

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

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

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

1.4 Зміст звіту.. 26

1.5 Контрольні питання. 27

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

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

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

2.3 Порядок виконання роботи.. 43

2.4 Зміст звіту.. 44

2.5 Контрольні питання. 45

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

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

3.2 Завдання до лабораторної роботи.. 47

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

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

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

4 Лабораторна робота №4 Поліноміальна апроксимація та методи точкового оцінювання.. 51

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

4.2 Завдання до лабораторної роботи.. 52

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

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

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

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

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

5.2 Завдання до лабораторної роботи.. 54

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

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

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

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

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

6.2 Завдання до лабораторної роботи.. 58

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

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

6.5 Контрольні питання. 59

ЛІТЕРАТУРА.. 60

ВСТУП

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

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

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

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

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

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

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

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

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

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

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

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

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

F = C₁*X₁+C₂*X₂+ C₃*X₃.

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

a₁₁*X₁ + a₁₂*X₂ +a₁₃*X₃ >= b₁;

a₂₁*X₁ + a₂₂*X₂ +a₂₃*X₃ >= b₂.

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

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

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

(1.1)

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

(i=1,m) (1.2)

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

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

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

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

Відомо також, що в монтажному просторі плати А може розміститися a₁₁ модулів М₁ і a₂₁ модулів М₂. На монтажній платі В може бути розміщено a₁₂ модулів М₁ і a₂₂ модулів М₂.

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

З урахуванням умов і вимог задачі складемо цільову функцію F = C₁*X₁+C₂*X₂ ® min, де Х₁ - кількість плат типу А, Х₂ - кількість плат типу В.

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

a₁₁*X₁ + a₁₂*X₂ >= b₁;

a₂₁*X₁ + a₂₂*X₂ >= b₂

де Х₁ і Х₂ - цілі числа.

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

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

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

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

(1.3)

за умов

(i=1,k); (1.4)

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

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

де a_ij, b_i, c_j - задані постійні величини і 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=(X₁,X₂...X_n), що задовольняють обмеженням (1.5) - (1.6), називається допустимим рішенням (або планом).

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

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

F(X) <= F(X*)

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

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

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

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

F = C₁*X₁+C₂*X₂+...+С_n*X_n, можна перейти до знаходження максимуму функції F₁ = -F = -C₁*X₁ - C₂*X₂ -... -С_n*X_n, оскільки min F = max (-F).

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

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

a_i1*X₁ + a_i2*X₂ +...+ a_in*X_n <= b_i

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

a_i1*X₁ + a_i2*X₂ +...+ a_in*X_n + X_n+i = b_i (X_n+i >= 0) (1.7)

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

a_i1*X₁ + a_i2*X₂ +...+ a_in*X_n >= b_i

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

a_i1*X₁ + a_i2*X₂ +...+ a_in*X_n - X_n+i = b_i (X_n+i >= 0). (1.8)

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

a_i1*X₁ + a_i2*X₂ +...+ a_in*X_n = b_i

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

a_i1*X₁ + a_i2*X₂ +...+ a_in*X_n <= b_i; (1.9)

-a_i1*X₁ - a_i2*X₂ -...- a_in*X_n <= -b_i.

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

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

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

X_k = U2k - V_k.

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

F = 3*X₁-2*X₂-5*X₄+X₅

за умов

2*Х₁+Х₃ - Х₄+Х₅<= 2;

Х₁-X₃+2*Х₄+Х₅ <= 3;

2*Х₂+Х₃-Х₄+2*X₅ <= 6;

Х₁ + Х₄-5*Х₅>= 8

X₁,X₂,X₃,X₄,X₅ >=0

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

2*Х₁+Х₃ - Х₄+Х₅+Х₆ = 2;

Х₁-X₃+2*Х₄+Х₅+Х₇= 3;

2*Х₂+Х₃-Х₄+2*X₅+Х₈ = 6;

Х₁ + Х₄-5*Х₅-Х₉ = 8

X₁,X₂...,Х₉ >=0.

Отже, дана задача може бути записана у формі основної задачі таким чином: максимізувати функцію F = 3*X₁-2*X₂-5*X₄+X₅ за умов

2*Х₁+Х₃ - Х₄+Х₅+Х₆ = 2;

Х₁-X₃+2*Х₄+Х₅+Х₇= 3;

2*Х₂+Х₃-Х₄+2*X₅+Х₈ = 6;

Х₁ + Х₄-5*Х₅-Х₉ = 8

X₁,X₂...,Х₉ >=0.

Приклад 1.4 Записати задачу, що полягає в мінімізації функції F = -X₁+2*X₂-X₃+X₄ за умов

2*Х₁ - Х₂ - Х₃ + Х₄ <= 6;

Х₁+2*X₂ + Х₃ - Х₄ >= 8;

3*Х₁ - Х₂+2*Х₃+2*X₄<= 10;

-Х₁+3*Х₂+5*Х₃-3*Х₄ = 15

X₁,X₂...,Х₄ >=0

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

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

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

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

F₁ = X₁-2*X₂+X₃-X₄ за умов

2*Х₁ - Х₂ - Х₃+ Х₄+Х₅ = 6;

Х₁+2*X₂ + Х₃ - Х₄-Х₆ = 8;

3*Х₁ - Х₂+2*Х₃+2*X₄+Х₇= 10;

-Х₁+3*Х₂+5*Х₃-3*Х₄ = 15

X₁,X₂...,Х₇ >=0.

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

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

за умов

= B_і (i=1,m), X_j>=0 (j=1,n).

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

F = C*X (1.10)

за умов

X₁*Р₁+X₂*Р₂+...+X_n*Р_n = Р₀; (1.11)

X >= 0 (1.12)

де С = (C₁,C₁...,C_n); X = (X₁,X₂...,X_n); C*X - скалярний добуток; Р₁,...,Р_n і Р₀ - m-мірні вектори-стовпці, складені з коефіцієнтів при невідомих і вільних членах системи рівнянь задачі:

b₁ a₁₁ a₁₂ a_1n

b₂ a₂₁ a₂₂ a_2n

Р₀ =.; Р₁ =.; Р₂ =.;...; Р_n =.

....

b_n a_m1 a_m2 a_mn

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

X₁*Р₁+X₂*Р₂+...+X_k*Р_k = Р₀ (1.13)

де все X_j>=0, то крапка X = (X₁,X₂...,X_k,0,...,0) є

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

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

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

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

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

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

F = C₁*X₁ + C₂*X₂ (1.14)

за умов

a_i1*X₁+a_i2*X₂ <= b_i (i=1,k) (1.15)

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

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

a_i1*X₁+a_i2*X₂ = b_i; (i=1,k);

X₁=0 і X₂=0.

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

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

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

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

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

Рисунок 1.1

Рисунок 1.2

Рисунок 1.3

Рисунок 1.4

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

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

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

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

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

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

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

5. Будують пряму C₁*X₁+C₂*X₂ = h, що проходить через багатокутник рішень.

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

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

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

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

Таблиця 1.1

Види комплектуючих	Витрата комплектуючих, шт, на один виріб	Загальна кількість комплектуючих, шт
А	В
I
II
III
Прибуток від реалізації одного виробу, грн.

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

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

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

12*Х₁ + 4*Х₂ <= 300;

4*Х₁ + 4*X₂ <= 120;

3*Х₁ + 12*Х₂ <= 252

X₁,X₂ >= 0.

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

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

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

12*Х₁ + 4*Х₂ = 300 (I)

4*Х₁ + 4*X₂ = 120 (II)

3*Х₁ + 12*Х₂ = 252 (III)

X₁ = 0 (IV)

X₂= 0. (V).

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

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

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

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

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

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

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

Рисунок 1.5

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

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

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

4*Х₁ + 4*X₂ = 120

3*Х₁ + 12*Х₂ = 252.

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

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

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

1. F=7*X₁+6*X₂ ® max; 2. F=3*X₁-2*X₂ max;

2*X₁+5*X₂ >= 10, 2*X₁+X₂<= 11

5*X₁+2*X₂ >= 10 -3*X₁+2*X₂ <= 10

X₁ <= 6, 3*X₁+4*X₂ >= 20;

X₂ <= 5; X₁,X₂ >=0.

X₁,X₂>=0.

3. F=5*X₁-3*X₂ ® min; 4. F=X₁+X₂ ® max;

3*X₁+2*X₂ >= 6, 2*X₁+X₂ <= 14

2*X₁-3*X₂ >= -6, -3*X₁+2*X₂ <= 9

X₁-X₂ <= 4, 3*X₁+4*X₂ >= 27;

4*X₁+7*X₂ <= 28; X₁,X₂ >=0.

X₁,X₂ >=0.

5. F=7*X₁-2*X₂ ® max; 6. F=2*X₁+2*X₂ ® max;

5*X₁-2*X₂ <= 3, X₁-2*X₂ >= 4

X₁+X₂ >= 1, 5*X₁+2*X₂ >= 10

-3*X₁+X₂ <= 3, 4*X₁-3*X₂ <= 12

2*X₁+X₂ <= 4; 7*X₁+4*X₂ <= 28;

X₁,X₂ >=0. X₁,X₂ >=0.

7. F=2*X₁+2*X₂ ® max; 8. F=2*X₁-4*X₂® max;

3*X₁-2*X₂ >= -6, 8*X₁-5*X₂ <= 16

X₁+X₂ >= 3, X₁+3*X₂ <= 2

X₁ <= 3, 2*X₁+7*X₂ >= 9;

X₂ <= 5; X₁,X₂ >=0.

X₁,X₂ >=0.

9. F=X₁+2*X₂ ® max; 10. F=3*X₁+3*X₂ ® max;

5*X₁-2*X₂ <= 4, X₁-4*X₂<= 4

X₁-2*X₂ >= -4, 3*X₁+2*X₂ <= 6

X₁+X₂ >= 4; -X₁+X₂ <= 1

X₁,X₂ >=0. X₁+2*X₂ >= 2;

X₁,X₂ >=0.

11. F=2*X₁-X₂ ® max; 12. F=5*X₁+X₂ ® min;

X₁-X₂ >= -3, X₁+7*X₂ >= 7

6*X₁+7*X₂ <= 42 -2*X₁+X₂ <= 6

2*X₁-3*X₂ <= 6, 2*X₁+5*X₂ >= 10

X₁+X₂ >= 4; 5*X₁+2*X₂ >= 10

X₁,X₂ >=0. 7*X₁+7*X₂>= 7

X₁ <= 6

X₂ <= 7;

X1,X₂ >=0.

13. F=X₁-X₂ ® max; 14. F=7*X₁+X₂ ® max;

-X₁+X₂>= 8, X₁+X₂ <= 14

8*X₁+5*X₂ <= 80, 3*X₁-5*X₂ <= 15

X₁-2*X₂ <= 2, 5*X₁+3*X₂ >= 21;

X₁+4*X₂ >= 4; X₁,X₂ >=0.

X₁,X₂ >=0.

15. F=7*X₁-X₂ ® min; 16. F=X₁+X₂ ® min;

X₁+X₂ >= 3, 3*X₁+X₂ >= 8

5*X₁+X₂ >= 5, X₁+2*X₂ >= 6

X₁+5*X₂ <= 5; X₁-X₂ <= 3;

0 <= X₁ <= 4; X₁,X₂ >=0.

0 <= X₂ >= 4.

17. F=X₁+3*X₂ ® max; 18. F=2*X₁+X₂ ® max;

-X₁+X₂ <= 3, X₁-X₂ >= 4

4*X₁+3*X₂ <= 20; X₁+X₂ >= 10

X₁,X₂ >=0. 4*X₁-X₂ <= 12

7*X₁+X₂<= 7;

X₁,X₂ >=0.

19. F=2*X₁+2*X₂ ® max; 20. F=2*X₁-4*X₂ ® max;

3*X₁-2*X₂ >= -6, 8*X₁-5*X₂ <= 16

X₁+X₂ >= 3, X₁+3*X₂ >= 2

X₁ <= 3, 2*X₁+7*X₂ <= 9;

X₂ <= 5; X₁,X₂ >=0.

X₁,X₂ >=0.

21. F=3*X₁+2*X₂ ® max; 22. F=X₁+X₂ ® max;

3*X₁+X₂ <= 21, X₁+2*X₂ <= 14

2*X₁+3*X₂ <= 30 -5*X₁+3*X₂ <= 15

2*X₁ <= 16; 4*X₁+6*X₂ >= 24;

X₁,X₂ >=0. X₁,X₂ >=0.

23. F=X₁+2*X₂ ® max; 24. F=-2*X₁+X₂ ® min;

4*X₁-2*X₂ <= 12, 3*X₁-2*X₂ <= 12

-X₁+3*X₂ <= 6 -X₁+2*X₂ <= 8

2*X₁+4*X₂ >= 16; 2*X₁+3*X₂ >= 6;

X₁,X₂ >=0. X₁,X₂ >=0.

25. F=2*X₁+3*X₂ ® min; 26. F=X₁+2*X₂ ® max;

2*X₁+X₂ >= 8, X₁+X₂<= 6

X₁+2*X₂ >= 6; *X₁+10*X₂ <= 26

X₁,X₂ >=0. X₁+11*X₂ <= 20;

X₁,X₂ >=0.

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

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

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

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

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

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

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

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

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

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

1.4 Зміст звіту

1.4.1 Сформульована мета роботи.

1.4.2 Постановка задачі ЛП згідно варіанту.

1.4.3 Результати роботи. Привести рисунок, аналогічний рис.1.5, побудований за допомогою Matlab.

1.4.4 Аналіз отриманих результатів і висновки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F = C₁*X₁+C₂*X₂+...+C_n*X_n

за умов

X₁ + A_1m+i*X_m+i +... + A_1n*X_n = B₁

X₂+ A_2m+i*X_m+i +... + A_2n*X_n = B₂

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

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

Нехай

(j=0,n).

Покладемо

(j=1,n); j = Z_j- C_j (j=1,n).

Оскільки вектори Р₁,Р₂...,Р_m - одиничні, то

X_ij = A_ij і Z_j = , а

j = .

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

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

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

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

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

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

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

Таблиця 2.1

Базис

C_б

Р₀

C₁

C₂

...

C_r

...

C_m

C_m+1

...

C_k

...

C_n

Р₁

Р₂

...

Р_r

...

Р_m

Р_m+1

...

Р_k

...

Р_n

Р₁

C₁

B₁

...

A_1m+i

...

A_1k

...

A_1n

Р₂

C₂

B₂

...

A_2m+i

...

A_2k

...

A_2n

Р_r

C_r

B_r

...

A_rm+i

...

A_rk

...

A_rn

Р_m

C_m

B_m

...

A_mm+i

...

A_mk

...

A_mn

m+1

F₀

…

D_m+1

…

D_k

…

D_n

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

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

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

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

Значення Z_j знаходиться як скалярний добуток вектора Р_j(j=1,n) на вектор С_б = (C₁,C₂...,C_m):

Z_j = , (j=1,n).

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

F_o= .

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

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

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

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

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

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

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

B_i-(B_r/A_r_k)*A_i_k при i<>r,

B_i' = (2.1)

B_r/A_r_k при i=r,

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

A_ij-(A_rj/A_r_k)*A_i_k при i<>r;

A_ij' = (2.2)

A_rj/A_r_k при i=r.

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

Таблиця 2.2

Базис

CБ

Р₀

C₁

C₂

...

C_m

C_m+1

...

C_k

...

C_n

Р₁

Р₂

...

Рr

...

Р_m

Р_m+1

...

Р_k

...

Р_n

Р₁

C₁

B’₁

...

A’_1r

...

A’_1r+1

...

A’_1n

Р₂

C₂

B’₂

...

A’_2r

...

A’_2r+1

...

A’_2n

Р_r

C_r

B’_r

...

A’_rr

...

A’_rm+1

...

A’_rn

Р_m

C_m

B’_m

...

A’_mr

...

A’_mm+1

...

A’_mn

m+1

F’₀

...

Z’_r-C_r

...

Z’_m+1-C_m+1

...

Z’_n-C_n

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

F_o' = F_o - (B_r/A_r_k)*D_k; (2.3)

D_j' = D_j - (A_rj/A_rk)* D_k (2.4)

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

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

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

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

У стовпцях в

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: