Алгоритм розв’язку задачі ЛП графічним методом

1. Побудова многогранника розв ’ язків.

Визначаємо область допустимих розв ’ язків (перетин півплощін, що відповідають, обмеженням задачі). Згідно з обмеженнями (3) многокутник розв ’ язків міститься у першому квадранті. Область допустимих розв ’ язків (ОДР) може бути поржньою множиною, опуклим многокутником або необмеженою многокутною опуклою областю.

У першому випадку задача ЛП не має розв ’ язків.

В другому – завжди існує точка (або точки), в яких цільова функція (1) набуває максимального або мінімального значення.

У третьому – лінійна функція (1) на ОДР може не досягти екстремуму.

Надалі, нехай ОДР не є порожньою множиною.

2. Будуємо вектор нормалі N=(c₁,c₂). Вектор нормалі вказує на напрямок зростання цільової функції (1).

3. Проводимо перпендикулярно до вектора нормалі N=(c₁,c₂) лінію рівня.

4. Визначення оптимальних крапок.

Для знаходження крапки максимуму цільової функції зміщуємо лінію рівня паралельно самій собі у напрямку вектора нормалі N доти, доки пряма не стане опорною до множини ОДР.

5. Обчислення оптимальних значень.

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

У загальному вигляді задача МП з двома змінними формулюється таким чином:

Z=f(x₁, x₂) →max/min (10)

За умов

g_k(x₁,x₂)≤ b_k к=1,2,......m (11)

x₁,x₂≥0 (12)

де f та g_k можуть бути лінійними або нелінійними.

При розв’язанні задачі (10) – (12) графічним методом важливим є поняття лінії рівня цільової функції.

Лінія рівня цільової функції називається така множина значень іі змінних, при яких функція набуває сталого значення f(x₁, x₂)=c:

- для лінійної функції f(x₁, x₂)=c=const – паралельні прямі;

- для квадратичної функції f(x₁, x₂)=(х₁)² +(х₂)² = c =const – концентричні кола різних радіусів r=(c)^1/2;

- для f(x₁, x₂)=a(х₁)² +b(х₂)² = c =const – концентричні еліпси.

 

Алгоритм знаходження розв’язку задачі МП графічним методом.

1. Знаходимо ОДР.

2. Будуємо лінії рівня цільової функції f(x₁, x₂)=c.

3. Визначаємо лінії рівня найвищого (найнижчого) рівня або встановлюємо нерозв’язність задачі із-за необмеженості цільової функції зверху (знизу) на ОДР.

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

Питання для самоконтролю.

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

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

3. Сформулюйте задачу ЛП в стандартній формі.

4. Запишіть задачу ЛП в матричній формі.

5. Запишіть задачу ЛП в векторній формі.

6. Дайте означення опорного плану задачі ЛП.

7. Дайте означення опуклої множини.

8. Дайте означення кутової точки.

9. Дайте означення області допустимих розв’язків.

10. Сформулюйте критерій кутової крапки многогранника розв’язків.

11. Як визначити кількість базових змінних?

12. Дайте означення базових та вільних змінних.

13. Дайте означення допустимого плану.

14. Дайте означення оптимального плану.

15. Що таке вектор нормалі цільової функції?

16. Дайте означення лінії рівня цільової функції.

 

Тема 3.Загальна задача лінійного програмування та деякі з методів її розв’язання

Лекція 3

Тема лекції: Вирішення задач ЛП симплекс-методом.

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

План лекції

1. Представлення задач ЛП в матричній та векторній формі.

2. Симплексний метод розв’язання задач ЛП. Теоретичні основи симплекс-метода.

3. Метод штучної бази.

 

Література:

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

2. Іванюта І.Д. Практикум з математичного програмування: Навчальний посібник/ І.Д. Іванюта, В.І. Рибалка, І.А. Рудоміра – Дусятська. – К.: «Слово», 2008. – 296 с.

3. Кучма М.І. Математичне програмування: приклади і задачі: Навчальний посібник/ М.І. Кучма. - Львів: «Новий Світ - 2000», 2006. – 344 с.

4. А. Черемис, Р. Юринець, О. Мищишин. Методи оптимізації в економіці. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 152 с.