і симплексного методу до рішенням двоїстої завдання. Будемо припускати, що завдання невирождени, тобто кожній кутовий точці безлічі Q 0 відповідає квадратна невироджених система рівнянь розмірності m, матрицю яку і називають двоїстим базисом прямий завдання. Разом з тим двоїстий симплекс-метод можна застосовувати при вирішенні задачі лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при рішенні задачі симплексним методом ці числа передбачалися невід'ємними). ​​
Відшукання рішення задачі двоїстим симплекс-методом включає в себе наступні етапи:
1. Знаходять псевдоплан завдання.
2. Перевіряють цей псевдоплан на оптимальність. Якщо псевдоплан оптимальний, то знайдене рішення завдання. В іншому разі або встановлюють нерозв'язність завдання, або переходять до нового псевдоплану.
3. Вибирають роздільну рядок за допомогою визначення найбільшого по абсолютній величині від'ємного числа стовпця вектора Р 0 і дозволяє стовпець за допомогою знаходження найменшого по абсолютній величині відношення елементів (m +1)-і рядка до відповідних негативних елементів роздільної рядка.
4. Знаходять новий псевдоплан і повторюють всі дії починаючи з другого етапу.
Двоїстий симплексний метод називають також методом послідовного уточнення оцінок, оскільки кутові точки завдання, що виникають при ітераціях, можна розглядати як наближені значення точної оцінки у *, тобто як наближені оцінки впливу умов завдання на величину мінімуму цільової функції. [2, c.87-92]
Значна частина економічних завдань, що відносяться до завдань лінійного програмування, вимагає цілочисельного рішення. До них належать завдання, у яких змінні величини означають кількість одиниць неподільної продукції, наприклад розподіл виробничих завдань між підприємствами, розкрій матеріалів, завантаження обладнання, розподіл судів по лініях, літаків по рейсах, а також завдання з виробництва неподільної продукції. Якщо одиниця становить малу частину всього обсягу виробництва, то оптимальне рішення знаходять звичайним симплексним методом, округляючи його до цілих одиниць, виходячи зі змісту завдання. В іншому випадку округлення може привести до вирішення, далекому від оптимального цілочисельного рішення.
Задача цілочисельного програмування формулюється так само, як і задача лінійного програмування, але включається додаткова вимога, яке у тому, що значення змінних, складових оптимальне рішення, повинні бути цілими невід'ємними числами.
Метод вирішення таких завдань, запропонований Гоморі, заснований на симплексному методі і полягає в наступному. Симплексним методом знаходиться оптимальний план задачі без обліку умови цілочисельності. Якщо оптимальний план цілочисельний, то обчислення закінчують; якщо ж оптимальний план містить хоча б одну дробову компоненту X i , то накладають додаткове обмеження, що враховує цілочисельн...
