ільки для допустимого базисного рішення системи, яке характеризується тією особливістю, що з
(n + m) обмежених за знаком змінних x, V, Y, l найбільше N змінних, де N=n + m - число рівностей в цій системі, відмінні від нуля.
Ідея методу Баранкина і Дорфмана полягає в тому, що процедура послідовного відшукання рішення починається з базисного рішення системи (1) - (3), яке не обов'язково задовольняє умові (4). Потім з використанням симплекс-методу домагаються рівності нулю опуклої функції xv + yl.
а) алгоритм:
Для зручності викладу всі змінні представимо у вигляді 2N - мірного вектора
=| | x, y, v, l | |.
Можна поставити відповідно кожному вектору z вектор z, який визначається співвідношенням
=| | v, l, x, y | |,
такий, що
z I=z i + N, z I + N=zi,=1,2, .., N,
xV + Y l=1/2zz.
За допомогою цих векторів, умови (1) - (4) запишуться у вигляді:
(5) (z)=zz=0, z? 0.
Виходячи з деякого допустимого базисного рішення системи (5), здійснимо послідовність симплекс перетворень, за допомогою яких будемо зменшувати опуклу функцію T (z)=zz, поки не досягнемо значення T=0.
Припустимо, є деякий допустимий базисне рішення системи (5). Симплекс - таблиця в даному випадку повинна задавати входять в базис змінні zg як функцію від N небазисних змінних z vh=th, що не входять в базис:
, g=1,2, .., 2N. (6)
цей запис можна використовувати і для небазисних змінних з числа zg. Для цього симплекс-таблиця доповнюється рядками, всі елементи якої (крім одного, рівного одиниці) дорівнюють нулю. У цих рядках для небазисной змінної zg=tj буде d gh=0, h=j, ad gj=1. Функціональну залежність (6) можна записати у векторному вигляді:
. (7)
При небазисних змінних th=0 формула (7) перепишеться у вигляді
=d 0? 0, T=d 0 d 0.
Далі t j =? > 0 і z=d 0 +? d j. Збільшуємо змінну tj поки деяка j-ая з базисних змінних не звернеться в нуль. Вона визначається з умови:
при dgi <0.
Тоді нове базисне рішення: z=d0 +? idj, а величина T відповідно
j=T +? jkj,
де Kj=2? j +? j? j,
де? j=djd0 і? j=djdj.
Очевидно, що kj <0. Якщо таких кілька, то вибирається те, якому відповідає найменший негативний твір? Jkj.
б) обчислювальна схема
Після визначення допустимого базисного рішення будують симплексну та додаткову таблиці у вигляді табл.1.
Таблиця 1.
На відміну від стандартної симплекс-таблиці тут додана таблиця для додаткових змінних? 0,? j,? j,? j, kj, які обчислюються за такими формулами:
? 0=T=d0d0=2? Di0di + N, 0
При? 0=0 відразу отримуємо оптимальне рішення. В іншому випадку додатково знаходимо:
? j =? (dijdi + N, 0 + di + N, jdi, 0), j=1, ..., N.
Далі для j, для яких? j < 0, визначаються:
? j=2? dijdi + N, j;
при dgj < 0.
Для визначення елемента j обчислюються:
<...
