Завдання лінійного програмування

Зміст

Вступ

1.Двовимірне завдання лінійного програмування

2. Графічний метод рішення

3.Приклад 1

4. Табличний симплекс-метод

5. Приклад 2

Література

Вступ

Тема контрольної роботи «Завдання лінійного програмування».

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

- двовимірне завдання лінійного програмування;

- методи рішення.

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

Їх можна розділити на:

- прийняття рішень в умовах визначеності - вихідні дані - детерміновані;

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

А за критерієм ефективності:

- одноцільове прийняття рішень (один критерій ефективності);

- багатоцільове прийняття рішень (декілька критеріїв ефективності).

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

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

1.
Двовимірне завдання лінійного програмування

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

Змінні прийнято позначати x₁
й x₂
. Розглянуте раніше завдання лінійного програмування є двовимірним.

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

Визначити значення змінних x₁
та x₂
, при яких лінійна цільова функція F досягає максимуму (мінімуму)

F=з1x₁
+з2x₂
→ max (min) (1.1)

при обмеженнях на змінні:

(1.2)

Серед обмежень можуть одночасно зустрічатися знаки >= , <= й =.

Коефіцієнти aij, bi, cj, i=1..m, j =1,2 будь-які дійсні числа (можливо й 0).

2. Графічний метод рішення

Двовимірні завдання лінійного програмування звичайно вирішуються графічно.

Алгоритм рішення задачи двумірного лінійного програмування графічним методом:

1. Будуємо область припустимих рішень функції F.

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

2. Будуємо пряму рівня.

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

3. Максимізуємо (мінімізуємо) цільову функцію F.

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

3.
Приклад 1

Вирішимо отримане двовимірне завдання лінійного програмування графічно:

Рішення:

Побудова області припустимих рішень цільової функції F

Побудуємо прямокутну систему координат, де вісь ОX позначимо за x₁
, а OY - за x₂
.

Тому що, відповідно до умови (3) x₁
й x₂
ненегативні, то можна обмежиться розгляданням першого квадранта.

Розглянемо перше обмеження:

3x₁
+4x₂
<=1700 (1)

Замінимо в даному обмеженні знак нерівності знаком рівняння й побудуємо пряму.

3x₁
+4x₂
=1700 (1')

Для цього знайдемо дві крапки, що належать даній прямій.

Нехай, наприклад, x₁
=0, тоді підставивши 0 в (1') одержимо 4x₂
=1700 або x₂
=425.

(0: 425) - координати першої крапки, що належить прямій.

Нехай x₂
=0, те 3x₁
=1700, отже, x₁
=567.

(567:0) - координати другої крапки, що належить прямій.

Відзначимо ці крапки на числових осях.

Аналогічно, для другого обмеження:

2x₁
+5x₂
<=1600 (2)

2x₁
+5x₂
=1600 (2')

При x₁
=0, x₂
=320 (0; 320)

При x₂
=0, x₁
=800 (800; 0)

Побудуємо дані прямі (на малюнку вони відповідно позначені (1') і (2')).

Тепер знайдемо на кресленні такі напівплощини, які відповідають нерівностям (1) і (2).

Пряма (1') 3x₁
+4x₂
=1700 ділить координатну площину на дві напівплощини. Одна напівплощина розташована вище прямої, друга нижче. Щоб знайти ту напівплощину, що відповідає нерівності (1), необхідно взяти будь яку крапку яка належить одній з напівплощин і підставити її координати в нерівність. Якщо нерівність буде вірною, то дана напівплощина є шуканою.

Наприклад, візьмемо крапку з координатами (0; 0) і підставимо її координати в нерівність (1) 3x₁
+4x₂
<=1700 або 0+0<=1700.

Виходить 0<=1700 - дана нерівність є вірною, отже, нерівності (1) задовольняє напівплощина, що лежить нижче прямої (1').

Аналогічно, надійдемо для нерівності (2) 2x₁
+5x₂
<=1600. Візьмемо крапку з координатами (0; 0).

Виходить 0<=1600 - дана нерівність вірна. Нерівності (2) задовольняє напівплощина, розташована нижче прямій (2').

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

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

Побудова прямої рівня.

Візьмемо довільну крапку, що належить області припустимих рішень - чотирикутнику ОАВС, наприклад, крапку М с координатами (100; 100). Підставимо координати крапки М у функцію F.

F(100; 100)=2*100+4*100=600.

Пряма рівня буде мати такий вигляд: 2x₁
+4x₂
=600

Побудуємо отриману пряму. Для цього необхідно знайти координати двох довільних крапок цієї прямої. Одна крапка в нас уже є - це крапка М(100; 100). Знайдемо ще одну крапку. Нехай x₂
=0, тоді x₁
=300. Отже, координати додаткової крапки (300; 0). Відзначимо отримані крапки й побудує пряму рівня (на малюнку 1 вона позначена (3')).

Значення функції F будуть зростати в міру того, як пряма рівня віддаляється від початку координат у позитивному квадранті. Напрямок зростання функції F буде збігатися з вектором, координати якого є коефіцієнтами при змінних x₁
й x₂
функції F. На малюнку - це вектор a{2; 4}, відкладений від крапки М.

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

Рис.1.Максимізація цільової функції F.

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

Знайдемо координати крапки B.

Дана крапка розташована на перетинанні двох прямих (1') і (2'), тому, щоб знайти її координати необхідно вирішити наступну систему рівнянь:

Із другого рівняння виразимо x₁

І підставимо отримане значення в перше рівняння.

(300; 200) - крапка, що відповідає оптимальному рішенню завдання, отже, максимальне значення становить 2*300+4*200=1400 умовних одиниць. Виходить, щоб дістати максимальний прибуток, необхідно випускати в тиждень триста одиниць моделі А и двісті одиниць моделі В.

4. Табличний симплекс-метод

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

Послідовність рішення симплексом-методом наступна:

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

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

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

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

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

A₁
x
₁
+.+A_n
x_n

+e₁
x_n

+e₁
x<sub>n

+1</sub>
+.+e_m
x<sub>n

+m</sub>

=A₀
=[a<sub>i

0</sub>
], (1.3)

Перетворення Гауса називають симплексним перетворенням, коли напрямний (базисний) елемент визначають за наступними правилами:

a) напрямний стовпець j
вибирають із умови, що в ньому є хоча б один позитивний елемент;

б) напрямний рядок і
вибирають так, щоб відношення було мінімально за умови що a_ij

>0

При такому перетворенні в базис вводиться вектор A_j

і виводиться вектор А_i

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

Для цього використають так називані оцінки векторів
:

(1.4)

де I_б
– множина індексів базисних векторів;

x_ij
- визначають із умови

(1.5)

Величини {∆_j

} рівні симплекс-різницям для змінних {x_j

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

з найбільшою по модулі негативною оцінкою, тобто

(1.6)

Для рішення завдання симплексом-методом на кожній ітерації заповнюють симплекс-таблицю.

5. Приклад 2

Вирішимо отримане двовимірне завдання лінійного програмування за допомогою симплекс-таблиць:Цільова функція F(x)=5x₁
+6x₂
→ min

Обмеженняx₁
+3x₂
≥15, 3x₁
+x₂
≥25

Складемо першу симплекс-таблицю.

У верхніх частинах осередків запишемо коефіцієнт цільової функції й обмежень:

Таблиця 1

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

Таблиця 1’

2. Обчислюємо зворотну величину λ=1/а_н
= 1/3 заносимо внижній правий кут осередку.

3. Всі елементи дозволеного рядка крім дозволеного елементу множимо на λ і результат записуємо в нижній правий кут осередків.

4. Всі елементи дозволеного стовпця крім дозволеного множеннимо на -λ і заносимо в нижній кут осередків. Підкреслимо отримані (нижні) числа в дозволеному стовбці й верхні числа в дозволеному рядку.

5. Запис у правому нижньому куті осередків таблиці 1

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

6. Переписуємо таблицю 1’ з урахуванням заміни x₂
на y₁
у таблицю 2.

Таблиця 2’

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

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

Таблиця 3

Получаємо

x₁
=15

x₂
=0

F(x)=5*15+6*0=75

Література

1. Системы автоматизированного проектирования. В 9-ти кн.Учебное пособие для вузов. Под редакцией Норенкова И.П. М.: Высш. шк., 1986.

2. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. Учебное пособие для вузов. - М.: Высш. шк., 1986.

3. П. Шеннен и др. Математика и САПР. т.1. М.: Мир, 1988.

4. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984.

5.Системы автоматизированного проектирования в радиоэлектронике. Справочник. М.: Радио и связь, 1986.

6. Погребной В.К. О декомпозиции графов на классы изоморфных подграфов. В кн.: Вопросы программирования и автоматизации проектирования. Изд. ТГУ, 1979, с. 82-96.

7. Петренко А.И. Основы автоматизации проектирования. К.: Техника, 1982. - 295 с.

8. Ильин В.Н.. Основы автоматизации схемотехнического проектирования. Г.: Энергия, 1979. - 392 с.

9. Демидович Б.П., Марон И.А. Основы вычислительной математики. Г.: Изд-во «Наука», 1966. - 664 с.

10.Разевиг В.Д. Система сквозного проектирования электронных устройств DesignLab 8.0.- М.: Изд-во «Солон»,1999. - 698 с.