Aj3, Aj4, Aj5, Aj6, Aj7, Aj8, Aj9, Aj10, Aj11, Aj12, Aj13).
Если ОДР початкової ЗЛП задана У ФОРМІ нерівностей типу (як в нашому випадка), то початковий базис может буті сформованому з Додатковий змінніх x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, обмежень, что вводяться в систему, з метою Приведення ее до канонічної форми рівності. У цьом випадка матриця P буде одінічною. Таким чином, віберемо як початковий базис XБО=(x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) T, оскількі стовпці A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19 матріці A утворюють одінічну матрицю. Тепер перейдемо до Заповнення симплекс-табліці. Нехай ЗЛП сформульована в канонічній ФОРМІ (7). Мі вибрать базісні змінні x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19. Дозволімо систему нерівностей в (7) відносно базисних змінніх. Система обмежень У ФОРМІ Такера набере вигляд:
x7=1500 - ();=585 - ();=390 - ();=323 - ();=525 - ();=330 - ();=451 - ();=825 - ( ); (9)=960 - ();=640 - ();=1200 - ();=380 - ();=300 - ();
Цільову функцію можна представіті у віді:
f (x)=f0 - (- 1141x1-1040x2-1318x3-684x4-2757x5-466x6), де f0=0.
Симплекс-таблиця віглядає таким чином:
Таблиця 3.3.1. Початкова симплекс таблиця поставленого Завдання
складах симплекс-таблиця відповідає початкова базису и початковій опорній точці ОДР. Перехід до чергової опорної точки в процесі поиска оптимального решение супроводжується Складання Нової симплекс-табліці.
Кожна симплекс-таблиця аналізується по крітеріях допустімості и оптімальності базису.
3.3.1 Перевірка ознакой допустімості и оптімальності базису
Ознака допустімості базису:
у опорній точці відповідно до (9) xj=bi, i=7,., 19; j=7,., 19, тому ознака допустімості базису формулюється як Умова bi0, i=7,., 19.
Ознака оптімальності базису:
Если для ті знайдення решение оптімальне и єдіно.
Если для ті знайдення решение оптімальне, альо НЕ єдіно.
Если ті решение неоптимальним. У цьом випадка поиск оптимального решение Триває и звітність, перейти до Нової опорної точки.
Перейдемо до конкретного випадка. У нашому випадка віконується Умова допустімості базису, оскількі b=(1500, 585, 390, 323, 525, 330, 451, 825, 960, 640, 1200, 380, 300) T <0 и bi <0 (i=7, ., 19).
Вибраний нами початковий базис XБО=(x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) T НЕ є оптимальним, оскількі c1=- 1144 <0, c2 =- 1040 <0, c3=- 1318 <0, c4=- 686 <0, c6=2757 <0, c7=466 <0. Таким чином, звітність, здійсніті Перехід до Нової опорної точки (нового базису).
3.3.2 Знаходження дозволяючого елемент в симплекс-табліці. Формування нового базису
Відповідно до симплекс-методу нова опорна точка вібірається Тільки среди сусідніх, тоб новий базис позбав однією змінною відрізняється від КОЛІШНИЙ. Таким чином, Формування нового базису здійснюється на базі КОЛІШНИЙ помощью виведення з нього одній з базисних змінніх xs и вступи однієї з вільніх змінніх xr.
Вибір змінної xr. Вибір змінної xr здійснюється за результатами АНАЛІЗУ Коефіцієнтів cj симплекс-табліці.
Знайдемо
cr =.
У нашому випадка min {c1, c2, c3, c4, c5...
