Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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





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

Множина D в n-мірному евклідовому просторі називається опуклою множиною, якщо для будь-яких двох точок цієї множини точки X = належать множині D для всіх значень X, які належать відрізку [0; 1]. Геометрично це означає, що якщо дві точки належать множині D то й відрізок прямої, що їх з’єднує, також належить до множини D. Прикладами опуклих множин на площині є відрізок, пряма, круг, півплощина, квадрат і т.д.

Розглянемо основні властивості розв’язків задач лінійного програмування.

Вектор Х=(х1, х2, ... , хп), координати якого задовольняють систему обмежень (3.2) і (3.3), називають допустимим розв’язком (планом) задачі. Сукупність допустимих розв’язків задачі утворює область допустимих розв’язків.

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

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

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



Розглянемо алгоритм графічного методурозв’язування задач лінійного програмування. Слід зауважити, що окреслений метод використовується для розв’язування певного класу задач лінійного програмування, зокрема задач, число невідомих яких не перевищує 3. Хоча вже в трьохвимірному просторі важко побудувати многогранник допустимих розв’язків, а задачу лінійного програмування, яка містить більше трьох змінних графічно зобразити практично неможливо. Тому найчастіше графічним методом розв’язують задачі лінійного програмування, які містять дві невідомі і записані в другій стандартній формі (з обмеженнями-нерівностями).

Розглянемо основні етапи знаходження розв’язку задач ЛП графічним методом:

1) На координатній площині Х12 будуємо граничні прямі, які відповідають системі обмежень задачі:

, i = .

2) Визначаємо півплощини, які є розв’язками нерівностей. Для цього беремо координата точки з довільної півплощини і підставляємо в нерівність. Якщо нерівність справджується, то півплощина розв’язків направлена в сторону вибраної точки, якщо ж не справджується, то в протилежну сторону.

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

4) Будуємо вектор нормалі , початок якого знаходиться в точці (0,0), а друга координата - в точці (с12) (коефіцієнти при невідомих в цільовій функції). Вектор нормалі вказує напрямок зростання функції.

5) Перпендикулярно до вектора нормалі будуємо лінію рівнів с1х1 + с2х2 = const. Для зручності знаходження оптимальних точок лінію рівнів будуємо так, щоб вона мала спільні точки з многокутником розв’язків (перетинала многокутник розв’язків).

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

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

Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой




Дата добавления: 2014-11-18; Просмотров: 1112; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.019 сек.