у перебору кутових точок, при якій для знаходження оптимального рішення досить досліджувати лише невелику їх частину. Ця процедура називається симплекс-методом . p> Дж. Данциг запропонував при переході від однієї крайньої точки до іншої заміняти в базисної матриці всього один вектор. Це означає, що при такому переході ми повинні одну з базисних змінних виключити - зробити її небазисной (рівною нулю), а на її місце ввести нову змінну з числа небазисних (нульових) - зробити її базисної (Позитивної). p> Виявляється, геометрично така заміна приводить до переходу від однієї кутової точки до суміжної (сусідньої), пов'язаної з попередньою точкою загальним ребром.
З усіх сусідніх точок вибирається та, в якій цільова функція зростає найбільше. Оскільки число кутових точок звичайно, через кінцеве число переходів буде знайдена вершина з найбільшим значенням цільової функції, або буде встановлена необмеженість цільової функції на необмеженій безлічі планів.
Загальна схема симплекс-методу складається з наступних основних кроків.
В· крок 0 . Визначення початкового базису і відповідної йому початкової кутової точки (базисного плану). p> В· крок 1 . Перевірка поточного базисного плану на оптимальність . Якщо критерій оптимальності виконаний, то план оптимальний і рішення закінчено. Інакше перехід на крок 2. p> В· крок 2 . Знаходження змінної, що вводиться до складу базисних. (З умови збільшення цільової функції). p> В· крок 3 . Знаходження змінної, виключається зі складу базисних змінних (З умови збереження обмежень задачі). p> В· крок 4 . Знаходження координат нового базисного плану (суміжній кутовий точки). Перехід на крок 1. p> Повторювані кроки 1-4 утворюють одну ітерацію симплекс-методу.
З цієї схеми випливає, що по-перше, для початку роботи симплекс-методу треба мати якусь кутову крапку - початковий базисний план, а по-друге, треба вміти досліджувати поточну кутову точку на оптимальність, що не обчислюючи всіх суміжних вершин. Ці проблеми легко вирішуються, якщо канонічна задача ЛП має якийсь спеціальний вид.
Визначення . Будемо говорити, що канонічна задача ЛП має "Доцільний вид", якщо
1. праві частини рівнянь,. p> 2. матриця умов містить одиничну підматрицю розміру
.
Іншими словами, в будь-якому рівнянні є змінна з коефіцієнтом рівним одиниці, відсутня в інших рівняннях. Перша умова не є обтяжливим, так як в випадку негативної правій частині деякого рівняння, досить помножити його на (-1). У задачі переважного виду початковий базисний план знаходиться дуже просто.
Приклад 2.1.
В В
Матриця умов A і вектор правих частин обмежень b мають вигляд
,,
а цільової вектор з = (1, -3, 0, 4, 2). p> Відразу очевидна одна базисна матриця: з одиничними векторами умов. p> Отже, вибираючи в як базисних змінних x <...
