Графічний метод для задач ЛП n-вимірного простору при - Розв'язання задач математичного програмування

Нехай кількість змінних N

Число обмежень M,

.

Дві з N змінних, наприклад Х1 та Х2 Вільні, інші M базисні

рівнянь вигляду:

Оскільки, то

,

(2.19.1)

Узявши величину Х3 рівною нулю, отримаємо рівняння:

.

Для такої прямої,

Відмітимо ту півплощину, де. Аналогічно ; ;...;. Спільна частина площини в - багатокутник допустимих розв'язків.

Необхідно знайти максимальне значення функціонала:

.

Підставивши, , ,...; з (2.19.1) у функціонал, отримаємо F через дві вільні змінні та :

,

Де -- вільний член. Далі відшукання оптимального плану здійснюється за алгоритмом для випадку двох змінних.

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

.

Розв'язання.

N = 7 -- кількість змінних, M = 5 -- кількість обмежень.

Вільні змінні Х1 та Х2 і виразимо через них всі базисні змінні.

(2.19.2)

, (2.19.3)

. (2.19.4)

;

.

Далі за алгоритмом беремо Х1 = 0 та Х2 = 0 -- координатні осі; інші обмежуючі прямі знаходимо, узявши Х3 = 0, Х4 = 0, Х5 = 0, Х6 = 0, Х7 = 0. Багатокутник допустимих розв'язків зображено на рис. 2.12.

Рис. 2.12

Знайдемо вигляд функціонала, вираженого через Х1 та Х2.

.

Відкидаючи вільний член, маємо: .

Будуємо вектор (-5, -2), а перпендикулярно пряму F.

Рухаючи пряму F в напрямку, протилежному (необхідно знайти мінімальне значення функції F), отримаємо точку мінімуму -- А (рис. 2.13).

Рис. 2.13

У точці А перетинаються дві обмежуючі прямі: Х6 = 0 та Х7 = 0.

= 8,5; = 5.

Звідки

= 0,5; = 16,5; = 17,5; = 0; = 0.

Підстановкою значень та в лінійну функцію F отримуємо значення цільової функції:

.

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

З властивостей розв'язків задачі лінійного програмування відомо: оптимальний розв'язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв'язків. Загальна кількість опорних планів визначається кількістю комбінацій.

1949 року американським вченим Дж. Данцігом запропоновано Симплекс-метод.

Похожие статьи




Графічний метод для задач ЛП n-вимірного простору при - Розв'язання задач математичного програмування

Предыдущая | Следующая