Розв’язати задачу лінійного програмування (ЗЛП) графічним методом

Задача 1. Розв’язати задачу лінійного програмування (ЗЛП) графічним методом.

[pic 1]

[pic 2]

[pic 3].

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

[pic 4]

Перетином напівплощин буде область, координати точок якої задовольняють умові нерівностей системи обмежень задачі.

Позначимо межі області рішень.

[pic 5]

Розглянемо цільову функцію завдання Z = x 1 + 2x 2 → min.

Побудуємо пряму, що відповідає значенню функції

Z = 0: Z = x 1 + 2x 2 = 0.

Вектор-градієнт, складений з коефіцієнтів цільової функції, вказує напрямок мінімізації Z (X). Початок вектора - точка (0; 0), кінець - точка (1; 2). Будемо рухати цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухаємо пряму до першого перетину позначеної області. На графіку ця пряма позначена пунктирною лінією.

[pic 6]

Пряма Z (x) = const перетинає область у точці A. Оскільки точка A отримана в результаті перетину прямих (4) і (5), то її координати задовольняють рівнянням цих прямих:

x 1 + 4x 2 = 4

x 1 = 0

Вирішивши систему рівнянь, отримаємо: x 1 = 0, x 2 = 1

Звідки знайдемо мінімальне значення цільової функції:

Z (X) = 1 * 0 + 2 * 1 = 2

Задача 2. Розв’язати ЗЛП симплекс-методом.

[pic 7]

[pic 8]

[pic 9].

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

У 2-й нерівності вводимо базисну змінну x 4. У 3-й нерівності вводимо базисну змінну x 5 зі знаком мінус. В 4-й нерівності вводимо базисну змінну x 6 зі знаком мінус. У 5-й нерівності вводимо базисну змінну x 7 зі знаком мінус.

2x 1 + 1x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 + 0x 7 = 10

1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 + 0x 7 = 2

1x 1 + 0x 2 + 0x 3 + 0x 4 -1x 5 + 0x 6 + 0x 7 = 0

0x 1 + 1x 2 + 0x 3 + 0x 4 + 0x 5 -1x 6 + 0x 7 = 0

0x 1 + 0x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 -1x 7 = 0

Введемо штучні змінні x: в 1-шу рівність вводимо змінну x 8; в 3-тю рівність вводимо змінну x 9; в 4-ту рівність вводимо змінну x 10; в 5-ту рівність вводимо змінну x 11;

2x 1 + 1x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 + 0x 7 + 1x 8 + 0x 9 + 0x 10 + 0x 11 = 10

1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 + 0x 7 + 0x 8 + 0x 9 + 0x 10 + 0x 11 = 2

1x 1 + 0x 2 + 0x 3 + 0x 4 -1x 5 + 0x 6 + 0x 7 + 0x 8 + 1x 9 + 0x 10 + 0x 11 = 0

0x 1 + 1x 2 + 0x 3 + 0x 4 + 0x 5 -1x 6 + 0x 7 + 0x 8 + 0x 9 + 1x 10 + 0x 11 = 0

0x 1 + 0x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 -1x 7 + 0x 8 + 0x 9 + 0x 10 + 1x 11 = 0

Для постановки задачі на мінімум цільову функцію запишемо так:

F (X) = -1x 1 -2x 2 + 2x 3 + Mx 8 + Mx 9 + Mx 10 + Mx 11 → min

За використання штучних змінних, що вводяться в цільову функцію, накладається так званий штраф величиною М, дуже велике позитивне число, яке зазвичай не задається.