русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


Основи графічного методу


Дата додавання: 2014-04-05; переглядів: 1183.


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

за умов

Припустимо, що система (2.14) за умов (2.15) сумісна і многокутник її розв'язків обмежений.

Згідно з геометричною інтерпретацією задачі лінійного програмування (2.4) кожне i-те обмеження-нерівність (2.14) визначає півплощину з граничною прямою . Системою обмежень (2.14) описується спільна частина, або переріз усіх зазначених півплощин, тобто множина точок, координати яких задовольняють всі обмеження задачі. Таку множину точок називають многокутником розв'язків, або областю допустимих планів (розв'язків) задачі лінійного програмування.

Умова (2.15) невід'ємності змінних означає, що область допустимих розв'язків задачі належить першому квадранту системи координат двовимірного простору. Цільова функція задачі лінійного програмування геометричне інтерпретується як сім'я паралельних прямих

Сформулюємо деякі властивості задачі лінійного програмування, застосовувані під час її графічного розв'язування.

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

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

Алгоритм графічного методурозв'язування задач лінійного програмування складається з розглянутих далі кроків.


<== попередня лекція | наступна лекція ==>
Модель має бути зрозумілою для користувача, зручною для реалізації на ЕОМ. | Будуємо прямі лінії, рівняння яких дістаємо заміною в обмеженнях задачі (2.14) знаків нерівностей на знаки рівностей.


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн