Роздрукувати сторінку
Главная \ Методичні вказівки \ Методичні вказівки \ 3801 Методичні вказівки до теми 3, Лінійне програмування, Оптимізаційні методи та моделі, НУХТ

Методичні вказівки до теми 3, Лінійне програмування, Оптимізаційні методи та моделі, НУХТ

« Назад

Тема 3. Лінійне програмування

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

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

2) Математичні рівняння та тотожності, які входять до складу моделі повинні теж бути лінійними (тобто невідомі змінні, які входять в модель можуть мати тільки першу ступінь).

3) Змінні, які входять в модель не можуть бути від’ємними.

Модель записується у такому виді:

І. Цільова функція (критерій оптимальності)

c– коефіцієнти при невідомих шуканих змінних  в цільовій функції (оптові ціни за одиницю продукції; собівартість одиниці продукції; питомий прибуток окремих видів продукції; питома рентабельність окремих видів продукції).

– шукані змінні більшою частиною означають обсяги випуску j виду продукції;

j – види продукції. 

ІІ. Система обмежень.

– коефіцієнти при невідомих змінних  в рівняннях та тотожностях (можуть бути: норми витрат сировини, матеріалів на одиницю продукції; оптові ціни за одиницю продукції та ін.);

– невідомі змінні;

– рівень обмежень у рівняннях та тотожностях (рівень ресурсів: матеріальних, сировинних, трудових і т.д.). 

ІІІ. Умови невід’ємності змінних 

На базі наведеного математичного опису можна проілюструвати суть цієї моделі так: необхідно визначити значення n невід’ємних змінних , які задовольняють обмеженням 3.2та забезпечують екстремальне значення (максимальне або мінімальне) цільової функції, яка виражена рівнянням 3.1.

До методів вирішення задач ЛП відносяться графічний метод, симплекс-метод. Симплекс-метод є аналітичним методом знаходження рішення задач ЛП.

Приклад. Графічним методом розв’язати задачу лінійного програмування:

Z= 3x1+7x2-5 (extr),

4x1 -3х2  12,

10x1 + 13х2  130,

- 6х1 + 8х2  48,

1 +5х2  10,

1 - х2  0,

х1  0,

х2 0.

Розв ’язування.

Будуємо граничні прямі, які відповідають нерівностям системи обмежень задачі (кожне обмеження розглядаємо як рівняння). Для побудови довільної прямої нам потрібно дві точки. Якщо права частина рівняння не дорівнює нулю, то для простоти знаходження координат двох точок, через які проходить гранична пряма (наприклад L1), беремо спочатку x1=0 iзнаходимо х2: 4·0–3х2=12, звідси –2=12, а х2= –4. Ми маємо координати однієї точки (0, -4). Потім підставляємо х2=0 і визначаємо х1: 13 0=12, звідси 1=12, а х1=3. Отже, координати другої точки (3,0). Аналогічно знаходимо координати точок для побудови граничних прямих L2, L3 та L4.

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

L1

4x1 -3х2 =12

(0;-4);

(3;0).

L2 :

10x1 + 13х2 =130

(0;10);

(13;0).

L3

- 6х1 + 8х2 =48

(0;6);

(-8;0).

L4:

1 +5х2 =10,

(0;2);

(5;0).

L5

1 - х2 = 0,

(0;0);

(1;4).

L6

x1=0,

вісь

Ox2.

L7

х2 =0,

вісь

Ox1.

Знаходимо півплощини розв’язків, що відповідають нерівностям системи обмежень. Для цього беремо довільну точку координатної площини, через яку не проходить гранична пряма 4x1 -3х2 = 12 (для простоти розрахунків візьмемо (0,0)) і підставляємо в першу нерівність. Отримаємо 4 0-3 0<12; 0<12, отже, нерівність справджується. А це значить, що півплощина розв’язків, яка відповідає першому обмеженню задачі, розміщена в напрямку точки (0,0). На рисунку вказуємо стрілкою, в якому напрямку від прямої L1розміщена півплощина розв’язків. Аналогічні розрахунки проводимо з усіма граничними прямими. Тільки для визначення півплощини розв’язків, що відповідає п’ятому обмеженню, беремо координати довільної точки, що не належить прямій, тільки не точку (0,0), оскільки гранична пряма L5 проходить через початок системи координат. Шукаємо спільну область, де перетинаються всі півплощини розв’язків. В нашому випадку багатокутником розв’язків є фігура ABCDE.

Будуємо вектор нормалі ={(0;0);(3;7)}. Перпендикулярно до нього - лінію рівнів. Паралельно переносимо цю лінію в напрямку вектора нормалі. Останньою вершиною багатокутника, яку перетне лінія рівнів є точка С - точка максимуму. Тоді паралельно переносимо лінію рівнів у напрямку, протилежному до напрямку вектора нормалі. Крайньою вершиною, яку перетне лінія рівнів, є точка А - точка мінімуму. 

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

10x1 + 13х2 =130,

- 6х1 + 8х2 =48,

Розв’язком системи є С(2.64; 7.97). Визначимо значення цільової функції в цій екстремальній точці Zmax =Z(C)=58.71.

Аналогічно визначимо координати точки мінімуму та відповідне значення цільової функції. Точка А є перетином прямих L4 та L5. Запишемо систему відповідних рівнянь та розв'яжемо її.

1 +5х2 = 10,

1 - х2 = 0,

Отже, А(0,45; 1,8). Zmm =Z (A) = 8,95. 

Приклад. Симплексним методом розв’язати задачу лінійного програмування: Для виготовлення двох видів продукції П1 та П2 використовуються три види сировини S1, S2 та S3. Запаси сировини, норми витрат сировини на виготовлення одиниці продукції кожного виду та оптова ціна одиниці продукції кожного виду наведені в таблиці: 

Вид сировини

Запаси сировини

Витрати сировини на виготовлення одиниці продукції

П1

П2

S1

275

4

5

S2

680

13

8

S3

60

1

1

Оптова ціна одиниці продукції

9

6

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

Розв'язування. Побудуємо математичну модель задачі. Нехай х1 та х2 - загальна кількість відповідно продукції П1 та П2; Z - сумарний дохід, який отримаємо від реалізації виробленої продукції. Тоді математична модель задачі матиме вигляд:

Z = 9х1+ 6х2 (max),

4x1 + 2  275,

13x1 + 8х2 680,

x1 + х2 60,

x1 0,

х2 0.

Приведемо задачу до канонічного виду:

Z = 9х1+ 6х2 (max),

1 + 2 3= 275,

13х1 +8х24 =680,

х1 + х2 + х5 = 60,

хi  0, i =.

Розв’яжемо цю задачу симплекс-методом. Заповнимо початкову таблицю:

Таблиця 3.1

№ таблиці

№ рядка

 

Опорний план

Коефіцієнти при невідомих

х1

х2

х3

х4

х5

1

0

Z

0

-9

-6

0

0

0

1

х3

275

4

5

1

0

0

2

x4

680

13

8

0

1

0

3

х5

60

1

1

0

0

1

Ітерація 1. В нульовий рядок заносимо інформацію про цільову функцію, а в рядки 1-3 - дані з відповідних рівнянь системи обмежень. Для заповнення нульового рядка початкової симплекс-таблиці цільову функцію запишемо в такому ж вигляді, як обмеження задачі, тобто у вигляді рівняння Z - 9х1 - 6х2 = 0 (всі невідомі перенесемо в ліву частину), і в подальшому нульовий рядок будемо заповнювати так само, як і рядки 1-3, що відповідають обмеженням. В стовпчику «Базис» записуємо базисні невідомі з системи обмежень, а для нульового рядка базисною невідомою є Z. В стовпчику «Опорний план» записуємо значення базисних невідомих, коли вільні невідомі х1 та х2 дорівнюють нулю (праві частини рівнянь-обмежень та цільової функції). В наступних стовпчиках записуємо коефіцієнти при невідомих в цільовій функції та системі обмежень.

Випишемо з першої таблиці початковий опорний план хопорн.=(0; 0; 275; 680; 60). Знайдемо значення цільової функції за цього плану Z(хопорн.)=9·0+6·0=0. Перевіримо, чи даний опорний план є оптимальним. Для визначення ступеня оптимальності опорного плану використовується нульовий рядок. Цільова функція досліджується на максимум, значить для оптимальності опорного плану в нульовому рядку не має бути від’ємних чисел. В задачі в нульовому рядку є два від’ємних числа ((-9) та (-6)), отже досліджуваний опорний план не є оптимальним. Вибираємо найменше з цих чисел (-9). Стовпець, в якому знаходиться це число є ключовим, а невідому x1, яка відповідає цьому стовпцю потрібно ввести в базис. Ставимо біля цієї невідомої стрілочку (якщо цільова функція мінімізується і в нульовому рядку є додатні числа, то вибираємо найбільше з цих чисел і за ним визначаємо, яку невідому потрібно ввести в базис). Щоб визначити, яку з невідомих потрібно вивести з базису, складаємо відношення елементів стовпця «Опорний план» до відповідних додатних елементів ключового стовпця і вибираємо найменше з цих відношень:

275 : 4 = 68,75;

680:13 = 52,3; (min)

60:l=60.

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

Ітерація 2. Переходимо до другої симплекс-таблиці. Замість невідомої х4 в базис вводимо невідому x1. На місці ключового елемента нам потрібно отримати 1, а всі інші елементи в стовпці повинні дорівнювати нулю. Для цього ключовий рядок ділимо на ключовий (генеральний) елемент, тобто на 13, і результат записуємо на місці другого рядка табл. 3.2. Усі інші рядки табл. 3.2 заповнюємо методом Жордана-Гауса, послідовно виключаючи невідому x1 з нульового, першого та третього рядків:

1) множимо всі елементи другого рядка на 9 і додаємо відповідні елементи нульового рядка табл. 3.1, результат записуємо на місці нульового рядка табл. 3.2;

2) множимо кожен елемент другого рядка на (–4) і додаємо відповідні елементи першого рядка табл. 3.1, результат записуємо на місці першого рядка табл. 3.2;

3) множимо кожен елемент другого рядка на (–1) і додаємо відповідні елементи третього рядка табл. 3.1, результат записуємо на місці третього рядка табл. 3.2.

Таблиця 3.2

№ таблиці

№ рядка

 

Опорний план

Коефіцієнти при невідомих

 

 

 

 

 

 

 

 

 

х1

х2

х3

х4

х5

 

2

0

Z

6120 13

0

-6

13

0

9 13

0

 

 

 

1

х3

855 13

0

33 13

1

-4 13

0

 

 

 

2

х1

680 13

1

8 13

0

1 13

0

 

 

 

3

х5

100 13

0

5

13

0

-1 13

1

Із таблиці виписуємо новий опорний план:

Xопорн =.

Значення цільової функції за такого опорного плану

Z(xопорн) = 470.77

Перевіримо цей опорний план на оптимальність. В нульовому рядку є від'ємне число (-6/13), тому такий опорний план не є оптимальним. Невідому, яка відповідає цьому стовпцю 2) вводимо в базис. Відмічаємо цю невідому стрілочкою. Складаємо відношення елементів стовпця «Опорний план» до відповідних додатних елементів ключового стовпця і вибираємо найменше з цих відношень:

(min). 

Невідому, яка відповідає цьому найменшому відношенню (в прикладі х5) виводимо з базису. Відмічаємо цю невідому стрілочкою. Ключовий елемент 5/13.

Ітерація 3. Переходимо до третьої симплекс-таблиці. Замість невідомої х5 в базис вводимо невідому х2. Ключовий (третій) рядок ділимо на 5/13 і результат записуємо на місці третього рядка табл. 3.3. Знову використаємо метод Жордана-Гауса, послідовно виключаючи невідому х2з нульового, першого та другого рядків:

1) множимо всі елементи третього рядка на 6/13 і додаємо відповідні елементи нульового рядка табл. 3.2, результат записуємо на місці нульового рядка табл. 3.3;

2) множимо кожен елемент третього рядка на (-33/13) і додаємо відповідні елементи першого рядка табл. 3.2, результат записуємо на місці першого рядка табл. 3.3;

3) кожен елемент третього рядка множимо на (- 8/13) і додаємо відповідні елементи другого рядка табл. 3.2, результат записуємо на місці другого рядка табл. 3.3.

Таблиця 3.3

№ таблиці

№ рядка

Базис

Опорний план

Коефіцієнти при невідомих

х1

х2

х3

х4

х5

3

0

Z

480

0

0

0

3

5

6

5

1

х3

15

0

0

1

1

5

-33

5

2

х1

40

1

0

0

1

5

-8

5

3

х2

20

0

1

0

-1

5

13

5

В нульовому рядку останньої таблиці немає від’ємних чисел, це означає наявність оптимального розв’язку: хопт=(40; 20; 15; 0; 0), Zmax = 480.

Отже, максимальний дохід становитиме Zmax=480, якщо продукції П1виготовити 40 одиниць (х1=40 ), а продукції П2 - 20 одиниць (х2=20).

Перевірка: Zmax= 9*40 + 6*20 = 360 +120 = 480. Невідомі х4=0 та х5=0, а це означає, що сировина S2 та S3 використана повністю, х3=15, значить сировина S1є в залишку (недовикористана) 15 одиниць.

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

З повагою ІЦ "KURSOVIKS"!