х 3 ;
- Z = - 2000 + (40/7) х 3 - (30/7) х 1 = - 2000;
Таблиця 3 ітерація
j
Базісні змінні
х 1
х 2
х 3
х 4
х 5
b i
q = b i /a ij
Конт-роль
1
х 2
0
1
14/35
0
-2/5
80
-
81
2
х 4
0
0
21/35
1
-13/5
60
-
59
3
х 1
1
0
-2/5
0
7/5
70
-
72
4
Z (x)
0
0
-28/7
0
-6
-2300
-
х 1 = 70 + (2/5) х 3 - (7/5) х 5 ; Z (x) - (28/7) х 3 - 6 Г— х 5 = -2300;
Z = 2000 + (30/7) (70 + (2/5) х 3 - (7/5) х 5 ) - (40/7) х 3 = 2300 - 6х 5 - (28/7) х 3 ;
- Z = - 2300 + 6х 5 + (28/7) х 3 = - 2300; х 3 = х 5 = 0. p> У цільовій Функції УСІ Вільні змінні від'ємні - опорний план Х * = (70; 80; 0; 60; 0) є оптимальним. Завдання розв'язано. br/>
Z * max = (-Z *) min = +2300.
Стереометрічно ідея методу Полягає у тому, что:
- знаходять будь-яку вершину багатогранніка розв'язків;
- рухаються Вздовж того з ребер, по якому функція зменшується (збільшується) до Іншої вершини багатогранніка розв'язків;
- як потрапляють у вершину, З якої у ВСІ боки функція зростає (спадає), так знаходять мінімум (максимум).
Нагадаємо ще раз:
- ЯКЩО вектор розв'язків задовольняє усім обмеженності, так ВІН має Назву планом;
- ЯКЩО план відповідає вершіні багатогранніка розв'язків (усі Вільні змінні дорівнюють нулеві), так ВІН має Назву опорного плану;
- ЯКЩО опорний план відповідає Єкстремальний значень цільової Функції, так ВІН має Назву оптимального плану.
Крітерій оптімальності за симплекс-таблиці.
Если форма мінімізується (максімізується) i у рідку цільової Функції відсутні додатні числа (від'ємні числа), за вінятком стовпчік опорний розв'язок (b 1 ), так опорний план є оптимальним.
КОЕФІЦІЄНТИ рядка цільової Функції інтерпретують як ПРИРІСТ цільової Функції при збільшенні Вільної невідомої на одиницю. Приріст додатній, ЯКЩО коефіцієнт від'ємній, и навпаки від'ємній, ЯКЩО коефіцієнт додатній.
Стовпець "j" є вірішальнім, як у цьом стовпцю, оцінка коефіцієнта при невідомій у цільовій Функції найбільша за модулем, тоб
ВЅ З j ВЅ = max.
Змінну "x j " у вірішальному стовпцю знаходять за співвідношенням
b i
min Вѕ = q, (f ij > 0; b i Ві 0);
a ij
Яке має Назву симплекса, что и Дає у свою черго Назву методу. Відповідній елемент a ij Назву ключового елемента, або центру табліці. p> Вільну змінну, яка відповідає вірішальному стовпчік, залучають до базисних змінніх, а базисних змінну, яка відповідає мінімальному симплекс, відповідно перетворюють на вільну змінну.
Елементи сімплексної рядки Нової табліці дорівнюють елементами старої табліці, поділенім на "a ij " - Ключовий елемент (центр). УСІ Другие елєменти вірішального стовпця прірівнюють до "0" (за віключенням ключового, якій дорівнює одініці) Шляхом жорданову Перетворення; це стосується такоже цільової Функції.
Можливі випадка розв'язку задачі лінійного програмування симплексному методом.
Нескінченна множини оптимальних планів можлива, ЯКЩО у строці цільової Функції оптимального плану хочай б одна вільна змінна має Нульовий оцінку (Обмеження паралельне цільовій Функції). Оптимальне решение у цьом випадка вірождене, тоб ранг системи рівнянь-обмежень більшій за кількість ненульовіх координат вектора розв'язків.
Необмеженість задачі лінійного програмування ...
