Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод одновременного решения пары двойственных задач

Читайте также:
  1. frac34; Методические основы идентификации типа информационного метаболизма психики.
  2. I . ОРГАНИЗАЦИОННО - МЕТОДИЧЕСКИЙ РАЗДЕЛ
  3. I. ЗАДАЧИ, РЕШАЕМЫЕ ОРГАНАМИ ВНУТРЕННИХ ДЕЛ ПРИ ЧРЕЗВЫЧАЙНОЙ СИТУАЦИИ
  4. I. Организационно-методические указания
  5. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  6. I. Решение логических задач средствами алгебры логики
  7. I. Флагелляция как метод БДСМ

Используя теоремы двойственности, можно, решив симплексным методом прямую задачу, найти оптимальное решение двойственной задачи. Метод одновременного решения пары взаимодвойственных задач заключается в следующем.

1. Обе задачи приводят к каноническому виду и устанавливают соответствие между переменными обеих задач.

2. Решают с помощью симплекс-метода ту из двух задач, где свободные члены в выражениях для базисных переменных неотрицательны (предполагается, что одна из задач таким свойством обладает).

3. На основании первой теоремы двойственности определяют оптимальное значение целевой функции второй задачи: или fmax = gmin.

4. На основании второй теоремы двойственности выписывают оптимальное решение второй задачи. Для этого целевую функцию первой задачи выражают через свободные, или неосновные, переменные. Тогда компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции прямой задачи, выраженной через неосновные переменные ее оптимального решения.

При использовании симплекс-таблиц из последней симплекс-таблицы выделяют последнюю строку, в которой числа, соответствующие переменным прямой задачи, присваивают компонентам оптимального решения двойственной задачи на основе соответствия переменных прямой и двойственной задачи.

Вернемся к примеру п. 4.3.

Прямая ЗЛП: Двойственная ЗЛП:

Канонический вид:

Установим соответствие между переменными двух задач:

Переменные прямой задачи I
Первоначальные Дополнительные
х1 y4 х2 y5 х3 y1 х4 y2 х5 y3
Дополнительные Первоначальные
Переменные двойственной задачи II
         

Первой решается прямая задача, поскольку для нее свободные члены в выражениях для базисных переменных неотрицательны:

х3 = 4 – х1 – 2х2,

х4 = 3 – х1 – х2,

х5 = 8 – 2х1 – х2.

Итоговая симплекс-таблица решения прямой задачи имеет вид:

сi БП          
х1 х2 х3 х4 х5 bi
  x2       -1    
  x1     -1      
  x5       -3    
D j            

 

Значение целевой функции двойственной задачи равно значению целевой функции прямой задачи: = = 10.

Оптимальное решение прямой задачи: = (2, 1, 0, 0, 3).

Оптимальное решение двойственной задачи: = (1, 2, 0, 0, 0), поскольку y1 «x3, y2 «x4, y3 «x5, y4 «x1, y5 «x2.

Таким образом, в соответствии со второй теоремой двойственности y1 = 1, y2 = 2, значения остальных переменных оптимального решения двойственной задачи y3, y4, y5 равны нулю, поскольку они не входят в выражение целевой функции.

Следует отметить, что положительным (ненулевым) компонентам оптимального решения одной из взаимодвойственных задач соответствуют нулевые компоненты оптимального решения другой задачи:


Дата добавления: 2015-12-07; просмотров: 61 | Нарушение авторских прав



mybiblioteka.su - 2015-2024 год. (0.006 сек.)