Двоїстий симплекс метод

 

Економіко-матиматичне моделювання ( готові шпаргалки )

 

Реферат на тему: Двоїстий симплекс метод

 

Оцінки отримані МНК мають властивості:

Як відомо, кожній задачі лінійного програмування можна поставити у відповідність двоїсту задачу. Для знаходження розв’язку однієї зі спряжених задач можна перейти до двоїстої і, використовуючи її оптимальний план, визначити оптимальний план початкової. Перехід до двоїстої задачі не обов’язковий. Звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках — двоїсту. Оцінками плану прямої задачі є рядок ( ), а оцінками плану двоїстої — стовпчик «План» з компонентами вектора вільних членів системи обмежень В.

Отже, розв’язуючи пряму задачу, симплексний метод дає змогу одночасно знаходити і розв’язок двоїстої задачі. Однак двоїсту задачу можна також розв’язати за таблицею, в якій записана пряма, а відшукавши оптимальний план двоїстої задачі, разом з тим отримати розв’язок початкової задачі. Такий спосіб розв’язання задачі лінійного програмування має назву двоїстого симплексного методу. Прямий та двоїстий симплексні методи пов’язані між собою. Розглянемо такий алгоритм двоїстого симплексного методу:

1. Необхідно звести всі обмеження задачі до виду «», ввести додаткові невід’ємні змінні, визначити початковий базис та перший опорний план .

2. Якщо всі оцінки векторів і компоненти вектора-стовпчика «План» для всіх , то задача розв’язана. Інакше необхідно вибрати найбільшу за модулем компоненту bl 0 і відповідну змінну xl виключити з базису.

3. Якщо в l-му рядку, що відповідає змінній xl, не міститься жодного , то цільова функція двоїстої задачі необмежена на багатограннику розв’язків, а початкова задача розв’язку не має. Інакше існують деякі і тоді для відповідних стовпчиків визначають аналогічно прямому симплекс-методу оцінки θ: ( ), що дає змогу вибрати вектор, який буде включено в базис.

4. Виконавши крок методу повних виключень Жордана—Гаусса, переходять до наступної симплексної таблиці (Переходять до пункту 2). Зазначимо, що для задачі знаходження максимального значення цільової функції за наведеним алгоритмом необхідно перейти до цільової функції F’=-F, або дещо змінити сам алгоритм.

Cторінки ( 1 )

 

Поисковый анализ сайта