Форми моделі ЗЛП та їх еквівалентність
Складові моделі ЗЛПФорми запису ЗЛПобщаястандартнаяОграничения Керовані змінні - будь-якого знака Цільова функція F (x)
Стандартна форма ЗЛП має канонічний вигляд, якщо в кожному рівнянні системи обмежень існує змінна з коефіцієнтом +1, причому в інших обмеженнях і в цільової функції цієї змінної немає, тобто коефіцієнт дорівнює 0. Канонічна форма називається допустимою, якщо все, інакше - неприпустимою. p> Алгоритм переходу до стандартної форми ЗЛП
Позбутися від змінних невизначеного знака. Для цього замінити кожне таке змінну різницею
, де
Зорієнтувати цільову функцію, враховуючи співвідношення
.
Використовуючи врівноважують змінні, перетворити наявні нерівності в рівняння.
Алгоритм переходу до канонічного виду стандартної форми ЗЛП
1. Позбутися від змінних невизначеного знака. Для цього необхідно замінити кожну таку змінну різницею
, де
Зорієнтувати цільову функцію, враховуючи співвідношення
В
В системі обмежень кожне рівняння без змінної, що створює канонічний вигляд, записати у вигляді двох нерівностей ().
Використовуючи врівноважують змінні, перетворити нерівності в рівняння.
При необхідності рівняння можна помножити на (-1).
Графічний метод розв'язання ЗЛП
Алгоритм розв'язання ЗЛП графічним методом
1. Побудувати область допустимих розв'язків: всім обмеженням системи обмежень ставлять у відповідність рівняння, для яких будують прямі; після чого визначають півплощини, що задовольняють вихідним неравенствам системи обмежень.
. Виділити штрихуванням область допустимих рішень (отримане опукле безліч).
Побудувати лінію рівня цільової функції.
3. Побудувати градієнт
, де.
Градієнт перпендикулярний лінії рівня.
4.Лінію рівня переміщаємо до крайньої точки допустимої області за напрямом градієнта (при завданні цільової функції на максимум) або антіградіента (при).
Визначити оптимальний план як точку перетину лінії рівня з крайньою точкою допустимої області. Знайти координати цієї вершини, вирішивши систему лінійних рівнянь тих прямих, які перетинаються в цій точці. Якщо змінних було більше двох, знайти інші значення. ol>
Обчислити значення F.
Зауваження: якщо у вихідній задачі більше двох змінних, то елементарними перетвореннями зводять завдання до двох змінним.
Сімплексні перетворення при зміні базисних змінних
Умовою для вирішення ЗЛП симплекс-методом є наявність моделі завдання, записаної в канонічному вигляді стандартної форми.
Для зручності рішення задачі складають таблицю
№ табліциБазісние змінні ... 0
...
В
...
В
...
...
...
...
...
В
...
...
Залежно від знаків (значень вільних членів, що стоять в правих частинах системи обмежень) і (коефіцієнтів цільової функції) можливі різні методи вирішення ЗЛП: основний, двоїстий і змішаний.
Алгоритм основного симплекс-методу (всі, але існують)
Записати в нульову початкову таблицю вихідну канонічну стандартну форму, взявши в якості базисних змінних ті, які створюють канонічний вигляд.
Серед негативних коефіцієнтів цільової функції () (при неіскусственное змінних) знаходиться максимальний по модулю. Відповідний стовпець над цим числом називається що дозволяє стовпцем (позначається *). p> Обчислити відносини правих частин обмежень () до позитивних елементів дозволяє стовпця по горизонталі і вибрати мінімальне відношення. Відповідний рядок називається роздільною рядком (позначається *). ol>
Елемент, що стоїть на перетині дозвільних рядка і стовпчика, називається що дозволяє елементом (виділяється?).
Переходимо до нової таблиці. Замінюється базисна змінна, що стоїть у роздільній рядку, на змінну, що стоїть в вирішуючому стовпці (тобто виходить новий базисний набір).
Заповнюються базисні стовпці (на перетині базисної змінної в рядку і стовпці коштує 1, а інші елементи в стовпці рівні 0).
Якщо існу...
