Припустімо, що задача лінійного програмування має такий вигляд:
і = с1 х1 + с2 х2 -" тах(тіп):
ацх1 ~т~ х2 - Ь1:
х1 > 0, х2 > 0.
Вважатимемо, що багатокутник розв'язків (область допустимих розв'язків) цієї задачі непорожній та обмежений. Тоді алгоритм графічного методу розв'язання задачі лінійного програмування складається з таких кроків.
1. На основі обмежень задачі в площині змінних Ох1 х2 будуємо
прямі, рівняння яких мають вигляд аі1 х1 + аі2х2 - Ьі = 0, і = 1, т.
• 2. Визначаємо ту частину площини, в якій виконується кожне з обмежень задачі.
• 3. Знаходимо багатокутник розв'язків задачі.
• 4. Будуємо вектор gradz = ^-i = cli + c2j, що задає на-
dxl <3x2
прям зростання цільової функції.
• 5. Проводимо пряму cl xl + c2 x2 = const, перпендикулярно до вектора grad z.
• 6. Рухаючи пряму clxl + c2x2 = const у напрямку вектора grad z (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв'язків, де цільова функція набуває екстремального значення.
• 7. Визначаємо координати точки, в якій цільова функція набуває максимального (мінімального) значення, й обчислюємо екстремальне значення цільової функції в цій точці.
Геометрична інтерпретація задач лінійного програмування можлива лише за наявності двох незалежних змінних. Якщо кількість змінних більша двох, зображення істотно ускладнюється або взагалі неможливе. Проте ідея одержання розв'язку, що лежить в основі графічного методу, зберігає зміст і для випадку багатовимірного простору.
На основі такої ідеї створений і розроблений один з основних точних методів розв'язання задач лінійного програмування - так званий симплекс-метод. Суть методу полягає в отриманні оптимального розв'язку шляхом перебирання допустимих розв'язків у такий спосіб, що на кожному кроці здійснюється перехід від одного допустимого розв'язку до наступного, яке за значенням цільової функції було б хоча б не гіршим за попереднє. При цьому перебираються лише вершини допустимого багатокутника.
Алгоритм симплекс-методу гарантує, що за наявності хоча б одного допустимого розв'язку за скінчену кількість кроків буде або одержаний оптимальний розв'язок, або доведена відсутність таких розв'язків.
Розглянемо послідовність дій під час реалізації цього алгоритму.
• 1. Модель практичної задачі лінійного програмування звести до канонічного вигляду за умови пошуку найбільшого значення цільової функції.
Сторінки
В нашій електронній бібліотеці ви можете безкоштовно і без реєстрації прочитати «Прийняття управлінських рішень» автора Автор невідомий на телефоні, Android, iPhone, iPads. Зараз ви знаходитесь в розділі „Задачі лінійного програмування“ на сторінці 2. Приємного читання.
