На головну

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

  1. Cегментація ринку. Основні завдання. Критерії сегментації на В2С ринку.
  2. ERP має виходи в зовнішнє середовище і призначена для вирішення завдань комплексного управління підприємством.
  3. I. ЗАВДАННЯ МЕДИЧНИХ ПРАЦІВНИКІВ В ЗАБЕЗПЕЧЕННІ МАРША
  4. I. Рішення логічних задач засобами алгебри логіки
  5. I.1.2. Цілі, завдання та види інженерних вишукувань.
  6. II. Рішення логічних задач табличним способом
  7. III Етап. Визначення функцій і завдань елементів системи якості

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

Почнемо розгляд геометричного відображення з одного рівняння з двома змінними:

1+ х2= 2.

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

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

       
 
   
 Можливий і інший шлях знаходження значень координат. Для цього потрібно просто розділити обидві частини рівняння на його вільний член. Стосовно до розглянутого прикладу: При такій формі запису в значеннях змінних показані відрізки, які відтинає пряма на осях коордінат.Еслі від розглянутого рівняння перейти до нерівності виду: 2х1 + х2 ? 2, (2.15) то його можна представити графічно, як це показано на рис. 2.2
 


х2


х1

0 1 2 3

рис.2.1

 З наведених малюнків видно, що якщо лінійне рівняння з двома невідомими є пряму лінію, то лінійне нерівність - полуплоскость.На малюнку 2.2 частина площині, яка задовольняє нерівності і розташована нижче прямої, заштрихована. Координати всіх точок, що належать заштріхованной площині, мають такі значення х1 і х2, Які задовольняють заданому нерівності. Ця напівплощина є областю допустимих рішень (ОДР).Введем В даний приклад додаткову умову невід'ємності змінних властиве завданням лінійного програмування, тобто х1?0; х2?0. в цьому випадку ОДР обмежиться площею заштрихованого трикутника (рис 2.3).
х2

3


1

х1


0 1 2 3

Мал. 2.2

х2

 Задамося тепер системою нерівностей: 2х1+2 х2 ? 12х1+2 х2 ? 8 (2.16) 4х1 ? 164х2 ? 12х1?0; х2?0Для зручності графічного побудови перепишемо систему, розділивши кожне нерівність на його вільний член:


3


1

х1


0 1 2 3

Мал. 2.3

 (А)

 (Б)

 (В)

 (Г)

х1?0; х2?0

 В результаті побудови (рис 2.4) визначилася область допустимих рішень системи, представлена ??у вигляді заштрихованого опуклого багатокутника з вершинами АВСDЕ. Оскільки в ОДР незліченна безліч точок, то розглянута система має безліч допустимих рішень. Для знаходження оптимального рішення потрібно задатися рівнянням цільової функції.
х2

7

6

а

 5 в

 3 Е D г

С

2

 1 б х1

 А В

1 2 3 4 5 6 7 8 9

Мал. 2.4

нехай:

 Z = 20х1 + 30х2Задамося деяким довільним значенням цільової функції, обчислимо щодо нього значення х1 і х2, А потім побудуємо на графіку лінію цільової функції: 20х1+ 30х2= 90; х1= 4,5; х2= 3. При завданні інших значень цільової функції на графіку проводились би відповідні їм прямі, паралельні зображеної. Виходячи з цього, для знаходження максимуму (оптимального рішення), слід переміщати паралельно самій собі пряму цільової функції до зіткнення її з найбільш віддаленої від початку координат вершиною багатокутника ОДР. У нашому прикладі це вершина С, для якої Z = 140 (х1= 4, х2= 2). Можна було б знайти оптимальний варіант вирішення і іншим способом. З цією метою слід було б обчислити значення цільових функцій для всіх вершин багатокутника, а потім вибрати з них найбільшу. Для умов нашого прикладу ZA= 0 (х1= 0, х2= 0); ZВ= 80 (х1= 4, х2= 0); ZС= 140; ZD= 130 (х1= 2, х2= 3); ZЕ= 90 (х1= 0, х2= 3) .Оптімальное рішення може бути і не єдиним. При зміні величини коефіцієнта при х2 з 30 на 40 в рівнянні цільової функції, найбільші і однакові між собою значення цільової функції будуть отримані в вершинах С і D (ZC= ZD= 160). Такий же результат може бути знайдений для будь-якої точки сторони багатокутника, що з'єднує названі вершіни.Еті варіанти рішень будуть відрізнятися значеннями входять до них змінних, але будуть характеризуватися однією і тією ж величиною цільової функції. Такі рішення називаються равнооптімальнимі.В закінчення наведемо узагальнене обгрунтування можливості застосування графічного методу розв'язання задач лінійного програмування. Такий метод може бути використаний при виконанні умови n-m = 2, стосовно канонічної формі запису системи обмежень. Наприклад, приведення нерівності (2.15) до зазначеної формі зажадало б введення однієї додаткової змінної. При цьому буде одне рівняння (m = 1) і три змінних (n = 3), тобто n-m = 2. Аналогічно, при приведенні системи (2.16) до канонічної формі - m = 3, n = 5 і n-m = 2. У загальному випадку, для будь-якої кількості рівнянь і змінних, виконання зазначеної умови забезпечить отримання графічного рішення на площині. При цьому дві будь-які змінні приймаються в якості вільних. Всі інші змінні розглядаються як базисні і виражаються через вільні. В результаті забезпечується побудова багатокутника ОДР в системі прямокутних координат.


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

1. Уявити графічно систему обмежень:

х1+ х2?2х1?0, х2?0Преобразуем систему: х1?1, х2?0
х2

3


1

х1


0 1 2 3

Мал. 2.5

На малюнку 2.5 видно, що немає таких значень х1 і х2, Які б задовольняли заданій системі обмежень. Отже, в даній системі відсутній ОДР. Системи обмежень, подібні розглянутій, називають несумісними.

2. Побудувати систему:

х1 + х2 ? 1

х1 ? 0, х2 ? 0

х2

3

2


1

 х1

1 2 3

Мал. 2.6

Вже згадана система приведена на рис. 2.6, з якого видно, що ОДР не обмежена зверху. У такому випадку при максимізації цільової функції рішення отримано бути не може, так як лінія цільової функції може нескінченно переміщатися в бік збільшення Z. Відповідно, при мінімізації цільової функції ОДР повинна бути обмежена знизу.

Рішення загальних завдань лінійного програмування при m-n = 2 є приватним практично вкрай обмеженим випадком. Користуватися геометричній інтерпретацією для відшукання рішення навіть при n-m = 3, тобто в тривимірному просторі, важко. При n-m = k> 3 геометрична інтерпретація втрачає наочність. Однак відповідна термінологія може виявитися зручною: можна говорити про область допустимих рішень, як про деяке «сверхмногогранніке» в просторі k вимірювань, обмеженому m «гіперплоскостямі»; про оптимальне рішення - як про одну з «вершин» цього багатогранника, про кожну «вершині» - як про «опорною точці» і т.д.

Незважаючи на те, що побудова для m-n = 2 відноситься до окремого випадку, з нього випливають певні висновки, які стосуються взагалі до властивостей вирішення основного завдання лінійного програмування.

1. Оптимальне рішення, якщо воно існує, не може лежати всередині області допустимих рішень, а тільки на її кордоні.

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

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

4. Завдання може не мати рішення навіть у випадку, коли існує ОДР.

 



Основне завдання лінійного програмування, її властивості, підхід до вирішення. | Симплексний метод розв'язання задач лінійного програмування.

Поняття методів вирішення. | Характеристика методів вирішення. | Порівняльна оцінка рішень. | Характеристика інформаційного процесу. Види і характеристика вхідної інформації. | Види і характеристика вихідної інформації. | Системний аналіз. Основи системного підходу до дослідження технічних об'єктів. | Загальна характеристика математичних моделей і методів обґрунтування рішень для технічних і виробничих систем. | Моделювання управління виробництвом. | Поняття лінійного програмування. Загальна математична постановка задачі лінійного програмування. | Математичні моделі типових задач лінійного програмування. |

© um.co.ua - учбові матеріали та реферати