вої функції. p>. Включення додаткових змінних. p>. Включення додаткових обмежень. p>. Двоїстий симплекс-метод. p>. Проблеми виродження, зациклення. br/>
1. Звернений базис, симплекс - множники
Розглянемо рішення ЗЛП симплекс-методом з точки зору алгебри. У матричному вигляді стандартна форма ЗЛП має вигляд:, Ах = b, де Аmxn. Уявімо матрицю А у вигляді В«склеєнихВ» двох матриць А = Вmxm Rmx (nm). Тут Вmxm - матриця, що складається з стовпців матриці А, відповідних змінним, які в оптимальній таблиці є базисними. Матриця Rmx (nm) складається з усіх решти стовпців. Припустимо відома матриця В-1. Помножимо зліва обмеження ЗЛП на В-1:
В-1 (ВR) x = B-1b, тут х = (хб.п., хсв.п.) (ЕmB-1R) x = B-1b x б.п. = B -1 b, х св.п. = 0.
У НДБР базисним змінним відповідає одинична матриця, тобто А = Сn-mEm. Так як А множиться на В-1, то У-1А = В-1 (Сn-mEm) = В-1 С В-1, що відповідає матриці коефіцієнтів оптимальної таблиці. Отже, в оптимальній таблиці в шпальтах тих змінних, які були засадничими у НДБР, знаходиться матриця В-1. p> Матриця В -1 називається звернений базис. У оптимальної таблиці В -1 знаходиться серед коефіцієнтів обмежень, що стоять у стовпцях тих змінних, які були засадничими у вихідній таблиці.
Запишемо тепер канонічний вигляд завдання.
xn + I, I = - врівноважують змінні.
С1х1 + ... + Сnxn = F (x)
Помножимо кожне обмеження на деяке число, відповідно і складемо з виразом цільової функції, отримаємо
х1 (С1 +) + ... + хn (Cn +) + + ... + = F (x) +
. (1)
Значення можна підібрати таким чином, щоб коефіцієнти перед базисними змінними дорівнювали нулю. Без обмеження спільності, наприклад, перші m змінних є базисними, тоді можна визначити з системи
.
Якщо припустити, що підібрали таким чином, що перед базисними змінними коефіцієнти рівні нулю, а перед вільними - невід'ємні, то вид (1) буде відповідати оптимальному увазі таблиці. Отже, в оптимальній таблиці коефіцієнти у виразі цільової функції перед змінними, які були засадничими у вихідній таблиці, є. Це і є симплекс - множники. При цьому,
.
Симплекс - множники - це такі числа , при множенні на які кожного обмеження, відповідно, і складення з виразом цільової функції буде отриманий такий вид цільової функції, що перед базисними змінними коефіцієнти рівні нулю , а перед вільними ненегативні.
Зауваження: якщо не всі коефіцієнти вільних змінних у виразі цільової функції невід'ємні, те це симплекс - множники проміжного рішення. p> Звернений базис і симплекс - множники дозволяють використовувати знайдене рішення ЗЛП, якщо відбуваються зміни умов завдання.
Приклад.
2. Зміна значень правих частин обмежень
Праві частини обмежень висловлюють обмежені обсяги ресурсів чи мінімальні норми споживання тощо Припустимо праві частини обмежень змінилися на. Іншими словами, постає завдання знайти новий оптимальний план, при b = b +. Чи можна використовувати результати вже вирішеною завдання? Якщо завдання було вирішено для колишнього значення b, то відомими є звернений базис В-1 і симплекс - множники. При цьому при визначенні В-1 і значення b ніяк не враховувалися, ці значення впливають лише на оптимальне значення цільової функції. Отже, нові значення цільової функції і змінних можна отримати за формулами
F (x) = -
В
Зауваження. Зазначений прийом можна використовувати лише при невеликих змінах в b, тобто базисне рішення повинно залишитися допустимим (ненегативним). Таким чином, якщо для базисних змінних отримано хоча б одне від'ємне значення, то рішення задачі можна продовжити двоїстим симплекс-методом. p> Приклад.
. Зміна значень коефіцієнтів цільової функції
Коефіцієнти цільової функції виражають ціни реалізації, вартість витрат і т.п. Якщо зміни відбулися в коефіцієнтах цільової функції, чи можна скористатися рішенням завдання з колишніми коефіцієнтами? Тобто, якщо j = Cj +, а змін до b не сталося, то і оптимальний план не зміниться, а зміняться лише опт імальние значення цільової функції та її коефіцієнтів. У вихідній таблиці цільова функція має вигляд
F (x) =-C1x1 - C2x2 - ... - Cnxn
Нехай в оптимальній таблиці базисними виявилися перші m змінних, отже, коефіцієнти перед ними в оптимальній таблиці повинні бути рівні нулю, виключимо ці змінні з виразу цільової функції. Щоб отримати вираз цільової функції оптимальної таблиці в загальному вигляді, використовують оптимальну таблицю. <В
Помножимо всі рівняння системи відповідно на С1, С2, ..., Сn і складемо з виразом цільової функції вихідної таблиці в загальному вигляді. Отримаємо
...
