но менше, ніж у попередній вершині.
Тепер виберемо як нового базису ненульові змінні x1, x3, x5. Їх необхідно виразити через вільні змінні x2 і x4. Це можна зробити так. Вважаючи x2 і x4 фіксованими, перенесемо їх в праву частину (7.14). Отримаємо систему з трьох рівнянь з трьома невідомими x1, x3, x5:
x1 + x3=300 - 5x2
x1=100 - x2 - x4
x1 + x5=160 - 3x2
Її легко дозволити: з другого рівняння
x1=50 - 0,5x2 - 0,5x4,
і підставляючи цей вираз в перше і третє рівняння, остаточно отримуємо
x1=50 - 0,5x2 - 0,5x4
x3=100 - 3x2 + 2x4 (7.17)
x5=60 - 2x2 + x4
Підставляючи ці вирази в (7.15), маємо
F=- 500- 7x2 + 5x4.
Оскільки коефіцієнт при x2 негативний, то і ця вершина не є оптимальною. Тепер ми повинні збільшувати x2, поклавши x4=0. З (7.17) маємо обмеження,
x2 lt; 50/(1/2)=100, x2 lt; 100/3=33.33, x2 lt; 60/2=30,
т.е. ми можемо збільшити x2 до 30 і отримати чергову вершину
x (2) 1=35, x (2) 2=30, x (2) 3=10, x (2) 4=0, x (2) 5=0.
в цій вершині F=- 710.
Тепер ми вибираємо ненульові змінні x1, x2, x3 як базисних, і висловлюємо їх через вільні змінні x4, x5. З (7.14) отримуємо
x1 + 5x2 + x3=300
x1 + x2=100 - x4
x1 + 3x2=160 - x5
Віднімаючи з третього рівняння другого, отримуємо
x2=60 + x4-x5, x2=30 + 0,5x4 - 0,5x5
Підставляючи це все в друге рівняння, маємо
x1=100-x4-x2=100-x4-30-0,5x4 + 0,5x5=70-0,5 * x4 + 0,5x5,
x1=35-0,75x4 + 0,25x5
Тепер перше рівняння дає
x3=300-4x1-5x2=300-140 + 3x4-x5-150-2.5 * x4 + 2.5 * x5=10 + 0,5x4 + 1,5x5,
Підставляючи ці вирази в (7.15) знаходимо
F=- 10 (35-0,75x4 + 0,25x5) - 12 (30 + 0,5x4 - 0,5x5)=- 710 + 1,5x4 + 3,5x5.
Тут коефіцієнти при x4, x5 позитивні, оскільки. е. знайдена вершина є точка мінімуму.
Отже, оптимальний план виробництва виходить при x1=35, x2=30.
Оскільки у вихідній задачі дві змінні, то її можна було вирішити графічно.
Наше рішення симплекс-методом відповідає руху по межі багатокутника з вершини A1 (0,0) в вершину A2 (50,0) і потім у вершину A3 (35,30).
7.3 Симплекс-таблиця
Усі математичні методи лінійного програмування засновані на знаходженні невід'ємних базисних рішень. Отже, перед нами стоїть завдання визначення неотрицательного базисного рішення. Нехай в системі лінійних рівнянь вільні члени всіх рівнянь - числа невід'ємні (в іншому випадку множенням обох частин рівняння на - 1 можна зробити вільний член позитивним). Будемо вирішувати систему методом повного виключення змінних.
Вихідна таблиця:
x 1 x 2 ... x j ... x n
a 11 a 12 ... a 1j ... a 1n b 1
......................
a i1 a i2 ... a ij ... a in b i
......................
a m1 a m2 ... a mj ... a mn b m
Рішення починається з вибору дозволяє елемента. Зробимо це наступним чином:
) за дозволяє стовпець приймемо такий стовпець, в якому є хоча ...
