Реферат Лінійне програмування

Тема: Контрольные работы

ustify"> Малюнок 2 - межі області рішень.

Розглянемо цільову функцію завдання F = x1 + x2? max.
Побудуємо пряму, що відповідає значенню функції F = 0: F = x1 + x2 = 0. Будемо рухати цю пряму паралельним чином. Оскільки нас цікавить максимальне рішення, тому рухаємо пряму до останнього торкання позначеної області. На графіку ця пряма позначена пунктирною лінією (Малюнок 3).
p align="justify"> Рисунок 3 - пошук максимального рішення.

Область допустимих рішень являє собою багатокутник.

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

Вирішивши систему рівнянь, отримаємо: x1 = 1.0769, x2 = 3.4615.

Звідки знайдемо максимальне значення цільової функції: (X) = 1 * 1.0769 + 1 * 3.4615 = 4.54.

.2 Рішення задачі ЛП симплекс-методом

Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.

Визначимо максимальне значення цільової функції F (X) = x1 + x2 при наступних умовах-обмежень:

(2)

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

Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:

Вирішимо систему рівнянь щодо базисних змінних:, x4,

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план: = (0,0,8,3)

БазісBx1x2x3x4x381210x436-101F (X0) 0-1-100

Переходимо до основного алгоритму симплекс-методу.

Ітерація № 0.

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

В якості ведучого виберемо стовпець, відповідний змінної x2, так як це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi/ai2

і з них виберемо найменше:

Отже, 1-ша рядок є провідною.

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