42063

Двойственность в линейном программировании (ЛП)

Лабораторная работа

Информатика, кибернетика и программирование

Цель работы изучить возможности табличного процессора MS Excel для решения двойственной задачи линейного программирования. Краткие теоретические сведения Двойственная задача ЛП Предположим что задача линейного программирования ЗЛП имеет вид: Составим другую ЗЛП число переменных которой равно числу ограничений данной задачи т. Если для второй задачи составить двойственную то получим первую задачу. сформулированные задачи составляют пару взаимно двойственных задач ЛП.

Русский

2015-01-19

223 KB

28 чел.

Лабораторная работа 2_1. Двойственность в линейном программировании.

Цель работы - изучить возможности табличного процессора MS Excel для решения двойственной задачи линейного программирования.

Краткие теоретические сведения

Двойственная задача ЛП

Предположим, что задача линейного программирования (ЗЛП) имеет вид:

Составим другую ЗЛП, число переменных которой равно числу ограничений данной задачи, т.е. m. Обозначим их . Тогда новая задача будет иметь вид:

  

Такая задача называется двойственной (сопряженной) для первой, а первая – прямой, или основной. Если для второй задачи составить двойственную, то получим первую задачу. Т.о., сформулированные задачи составляют пару взаимно двойственных задач ЛП.  

В общем случае схема формирования двойственной задачи следующая:

  •  Коэффициенты бывшей ЦФ становятся правой частью ограничений
  •  Правая часть ограничений становится коэффициентами новой ЦФ
  •  Матрица коэффициентов ограничений транспонируется
  •  Направление оптимизации меняется на противоположное.

Ввод зависимостей для двойственной задачи (пример из предыдущей лабораторной работы) показан ниже на рис.3.1

    Рис.3.1.

Левая часть ограничений есть произведение матрицы коэффициентов ограничений на вектор переменных (используется функция МУМНОЖ). ЦФ записывается как  произведение транспонированного вектора коэффициентов ЦФ на вектор переменных.

Рис.3.2. Экранная форма с условиями двойственной задачи

Ниже на Рис.3.3 окна Поиск решения приведены ограничения  на переменные и критерий оптимальности.

    Рис.3.3.

Результат решения двойственной задачи приведен на Рис. 3.4

Рис.3.4. Результаты решения двойственной задачи

Открыв отчет по устойчивости, можно увидеть новые двойственные оценки (Теневая цена) и убедиться, что значения переменных при решении задачи на максимум становятся двойственными при решении задачи на минимум, и наоборот.

Замечание. 

  •  При формировании двойственной задачи все неравенства системы ограничений прямой задачи следует привести к одному направлению: “” в задаче на минимум и “”  в задаче на максимум.
  •  Если в системе ограничений основной задачи имеется равенство (уравнение), то та переменная , которая соответствует этому i-ому ограничению-равенству, может быть произвольного знака.
  •  Если на некоторую переменную   основной задачи не наложено условие отрицательности, то соответствующее ей ограничение двойственной задачи является равенством.

Контрольные упражнения. Варианты.

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

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

 

А также другие работы, которые могут Вас заинтересовать

66648. Поведение как предмет психологии. Бихевиоризм и необихевиоризм 118 KB
  Развитие поведения происходит путем приобретения новых реакций через образование связей между условными и безусловными стимулами. Утвердившее в качестве предмета психологии поведение понятое как совокупность реакций организма обусловленная его общением со стимулами среды к которой он адаптируется.
66649. Проблема бессознательного в психологии 109 KB
  Высокоорганизованным существом человека сделает его разум. Разум и благо и проклятие человека одновременно; он принуждает его вечно решать задачу неразрешимой дихотомии. Но с другой стороны сознание как доминирующий элемент сложной человеческой системы явилось началом духовного возрождения человека.
66650. Учение Рене Декарта 142 KB
  Свои основные произведения Декарт написал в 20 - 40-х годах ХVII в., но уяснить их содержание невозможно без учета огромных изменений в европейской, прежде всего западноевропейской, истории в период Возрождения, начавшегося в Италии уже...
66652. Олигополия. Отличительные черты олигополии 129.5 KB
  Такой тип олигополии в условиях которой действуют фирмы производящие однородный продукт называется чистой олигополией. Олигополия в условиях которой фирмы выпускают дифференцированную продукцию называется дифференцированной олигополией.
66654. Гай Смит и Soil Taxonomy 232.86 KB
  Гай Смит – одна из наиболее значимых фигур в истории не только американского, но и мирового почвоведения. Его ключевая работой является классификация Soil Taxonomy. Разработка почвенной таксономии часто вызывала очень сильную критику.
66655. Управление качеством в сфере здравоохранения 82.5 KB
  В настоящее время в РФ сложилась система обеспечения качества медицинской помощи основанная на процедурах вневедомственного и внутриведомственного контроля качества медицинской помощи. Внутриведомственный контроль предусматривает применение мер административного воздействия...
66656. Процедура и методы оценки качества услуг 71.5 KB
  По физико-статистическим признакам и процедурам методы контроля и оценки качества подразделяют на пять групп: инструментальный, органолептический, модельно-расчетный, экспертный и социологический. В силу неосязаемости и несохраняемости услуг наибольшее распространение получили методы, относящиеся к последним трем группам.