Двоїстий симплекс метод. Приклад розв'язку задачі лінійного програмування двоїстим симплекс методом

Двоїстий симплекс метод, як і симплекс метод, використовується для знаходження розв'язку задачі лінійного програмування, записаної в основній формі, де серед векторів існує одиничних. Якправило, при використанні симплекс методу, значення стовпця вільних членів задовільняє умову додатності. Двоїстий симплекс метод використовується в тому випадку, коли серед вільних членів системи обмежень існують такі, що приймають від'ємні значення.

Розглянемо задачу лінійного програмування, яка полягає у визначенні максимального значення функції мети:

при обмеженнях:

Читати повністю

Програмна реалізація Симплекс методу на Delphi

Програма виконаний в середовищі Delphi 7 і призначена для розв'язання задачі лінійного програмування за симплекс методом. Отже, розглянемо конкретний приклад задачі такого типу, і спробуємо розв'язати її з допомогою даної програми.

Нехай потрібно знайти максимальне значення функції мети 112 при обмеженнях:

22

Запишемо систему обмежень у канонічній формі і побудуємо початкову симплекс таблицю:

Читати повністю

Розв'язок задачі лінійного програмування за симплекс методом

Ідея побудови розв'язку задачі лінійного програмування за симплекс методом полягає у переході від одного опорного плану до іншого, при якому значення цільової функції збільшується. Перехід до іншого опорного плану можливий лише в тому випадку, якщо відомо, деякий, початковий план.

Розглянемо задачу лінійного програмування виду:

при обмеженнях:

Дану задачу запишемо у векторній формі:

Читати повністю

Знаходження оптимального плану транспортної задачі методом потенціалів

Для знаходження оптимального плану транспортної задачі необхідно спочатку визначити опорний план перевезень з допомогою методу північно-західного кута чи методу мінімального елемента.

Теорема: Якщо Метод потенціалів — деякий опорнй план транспортної задачі, для якого виконуються наступні обмеження, а саме:

Метод потенціалівдля Метод потенціалів

Метод потенціалівдля Метод потенціалів

тоді даний опорний план є оптимальним. Метод потенціалів — називаються потенціалами пунктів відправлення та пунктів призначення.

Читати повністю

« Попередня сторінка