Дослідження операцій

1. Загальна задача ЛП. Допустима область та її властивості. Поняття вершини допустимої області, базисного (опорного) плану задачі.

https://bibl.kma.mk.ua/pdf/posibnuku/226/5.pdf

2. Стандартна задача ЛП. Зведення загальної задачі до стандартної. Канонічна задача ЛП. Зведення стандартної задачі до канонічної.

Математична модель загальної задачі лінійного програмування має вигляд:

(1)

(2)

(3)

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

Якщо точка задовольняє умови (2) і (3), то її називають допустимою точкою або планом задачі. Якщо точка задовольняє умову , то її називають оптимальною точкою або оптимальним планом задачі.

У випадку коли область допустимих значень необмежена, то не завжди буде досягатися мінімальне або максимальне значення. Задача лінійного програмування може мати багато розв’язків або може не мати жодного, може бути і єдиний розв’язок. Розв’язок задачі на max (min) існує тоді і тільки тоді, коли лінійна форма (цільова функція) обмежена зверху (знизу) на області допустимих значень.

Математична модель стандартної задачі лінійного програмування має вигляд:

(1)

(2)

(3)