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

Розглянемо найпростіший випадок n=2.

Така задача називається плоскою. Кожна нерівність системи обмежень визначає частину площини, що лежить вище (нижче) відповідної прямої. Уся система обмежень визначає на площині х₁, х₂ багатокутник, що називається припустимою областю (припустимою множиною) задачі.

Кожна точка Р(х₁, х₂ ) усередині цієї множини і на її межі визначає припустимий план задачі. Необхідно з усіх припустимих планів задачі знайти найкращий (оптимальний).

Вектор є градієнтом функції F і перпендикулярний до лінії рівня F=const.

Проведемо лінію рівня F=0 - пряма l: с₁х₁ + с₂х₂ = 0 проходить через початок координат. Побудуємо у точці О(0;0) і виконаємо паралельне перенесення прямої l у напрямку . У процесі перенесення пряма проходить через різні точки припустимої множини. Точка, у якій відбувається останнє торкання цією прямою області (точка «прощання») і визначає оптимальний план задачі. Якщо «прощання» відбувається по стороні багатокутника, кожна її точка дає оптимальний план; задача має безліч рішень. Якщо такої точки не існує, задача не має рішень.

Приклад

А (0;2); В (1,5;1); С (2;0)

Припустима множина: чотирикутник ОАВС. Точка «прощання» В (1,5;1).

Оптимальний план

2. Розглянемо задачу лінійного програмування в канонічній формі

(2.1)

(2.2)

; j= 1,... n (2.3)

Введемо в розгляд матриці

Задача набуде наступного вигляду:

F = С • X"max (2.4)

А• Х=У (2.5)

X ≥ 0 (2.6)

Система обмежень (2.2) і (2.3) (або (2.5) і (2.6)) задає припустиму множину - багатогранник (симплекс) у n-мірному просторі.

Точка максимуму знаходиться в одній з вершин багатогранника.

Ціль симплекса-методу: за найменше число кроків знайти цю вершину.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Задачі лінійного програмування та методи їх розв’язування	\|	Алгоритм симплекс-методу

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.006 сек.