Тема 2.Загальна задача лінійного програмування та деякі зметодів її розв’язування Лекція 4 Тема лекції: Графічний метод розв’язування задач лп.

Мета: ознайомити студентів з графічми методом вирішення задачі ЛП

План лекції

1. Графічиний метод розв’язування задач ЛП з n=2.

2. Графічний метод розв’язування задач ЛП з n≥2 (n-m=2).

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

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

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

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

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

1. Графічний метод розв’язання задач ЛП n=2.

Загальна задача ЛП геометрично інтерпретується так: кожне k – те обмеження – рівність

a_k1x₁ + a_k2x₂ + a_k3x₃ + …….+ a_knx_n= b_k (k=1,….m)

задає в n – вимірному просторі основних змінних х₁,х₂,х₃…..х_к, ....... х_n гіперплощину, а кожне k – те обмеження – нерівність

a_k1x₁ + a_k2x₂ + a_k3x₃ + …….+ a_knx_n ≤ b_k (k=1,….m), визначає деяку ггіперплощину та півпростір n – вимірного простору, що лежить на один бік від цієї гіперплощини. За умоми сумітності системи нерівностей задачі ЛП, перетин усіх цих півпросторів як опуклих множин, утворює опуклий многогранник допустимих розв’язків. Кожна вершина цього многогранника розв’язків визначає опрний план.

Розглянемо геометричну інтерпритацію задачі ЛП для випадку n=2.

Приклад 1. Розв’язати задачу ЛП графічно.

2х₁ + 3х₂≤12

2х₁ - х₂≤4

х₁,х₂≥0

а) z =3х₁ + х₂→max

b) z =х₁ + 5х₂→max

c) z =4х₁ + 6х₂→max

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

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

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

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

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

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

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

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

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

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

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

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

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