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

Задачу лінійного програмування формулюється так. Знайти:

В даному випадку всі умови мають вид нерівностей. Іноді вони можуть бути змішаними, тобто нерівності і рівність:

В матричній формі задачу лінійного програмування записують таким чином.

Найти

Допустимою безліччю рішень задачі називають будь-яку множину До значень

задовольняючих приведеним вище умовам лінійного програмування, т.е.

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

ПРИКЛАД 1найти за умов

 

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

 

 

 

 

800 X

 

Мал. 9.6. Многогранник рішень в геометричній інтерпретації задач лінійного програмування

 

Тепер розглянемо цільову функцію, яка має вигляд:

f (x1, x2) = 2x1+5x2.

Хай f (x1, x2) = 1000 = z.

Графік рівняння 2x1+5x2 = 1000 є прямою з відрізками на осях х1 = 500 одиниць, а х2 = 200 одиниць.

При f (2x1+5x2) = 1500, отримаємо пряму z, що має рівняння:

Пряма z паралель прямій z, але розташована вище її. Рухаючи пряму вгору паралельно самої собі, приходимо до такого положення z mах, коли пряма і множина К, матимуть тільки одну загальну крапку А. Очевидно, що крапка оптимальне рішення, оскільки вона лежить на прямій з максимально можливим значенням z.. Помітимо, що ця крапка виявилася крайньою точкою множини К.

 








Дата добавления: 2016-06-13; просмотров: 841;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.