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.  

 

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

5250. Отделочные и штукатурные работы 141.5 KB
  Отделочные работы, включающие в себя штукатурные, облицовочные, малярные, стекольные, обойные работы и устройство полов, являются завершающими в общем комплексе строительных работ, и от их качественного выполнения во многом зависит общая..
5251. Решение проблем Чечни вооруженным путем 250.5 KB
  Введение Внутренний вооруженный конфликт на территории Чеченской республики заставил по-новому взглянуть на все, существующие на сегодня положения, обуславливающие боевое применение войск и их боевое обеспечение, высветил в полной мере специфику под...
5252. Маркетинг. Паблик рилэйшнз. PR. Маркетинговая политика фирмы и ее имидж 1007 KB
  Многообразие определений понятия Паблик рилэйшнз: современное состояние проблемы. Паблик рилейшнз определений PR. Такое разнообразие определений вызвано, тем, что PR – это постоянно развивающаяся система, а разнообразие ее опис...
5253. Ленточный транспортер и его проектирование 234.43 KB
  Ленточный транспортер Цель работы: Произвести расчеты транспортера и спроектировать редуктор. Содержание Задание Введение. Назначение, область применения и краткое описание изделия. Расчетная часть: - Кинематический расчет - Расчет...
5254. Обеспечение безопасности в туристических поездках 83.5 KB
  Введение Актуальность темы исследования Обеспечение безопасности в туристических поездках обусловлена тем, что туристская поездка практически всегда содержит элементы нового и существенно отличающегося от привычной среды обитания, в том числе и т...
5255. Выбор диодов СВЧ для конкретного применения 575.5 KB
  Выбор диодов СВЧ для конкретного применения Выполнить: Указать выбранные типы, обеспечивающие лучшее качество работы, и указать название, автора и страницы справочника. Указать функциональное назначение выбранных типов диодов. Прив...
5256. Проектирование двухступенчатого цилиндрического редуктора с косозубыми колесами 179.34 KB
  Техническое задание Определить исходные данные для проектирования двухступенчатого цилиндрического редуктора с косозубыми колесами в быстроходной (б) и прямозубыми колесами в тихоходной (Т) ступени рис. 1. Подобрать двигатель, определить перед...
5257. Параллельный метод для нахождения плана распределения каналов 102 KB
  Цель работы Изучить параллельный метод для нахождения плана распределения каналов (ПРК), который является приближенным. Такой метод зачастую используется при большом числе узлов. Задание Требования задаются числом каналов между различными парами узл...
5258. Зарубежное инвестирование 65.5 KB
  Вопрос №1. Дайте определение прямых инвестиций. Охарактеризуйте основные мотивы прямого зарубежного инвестирования, назовите его формы. Какие выгоды получает от вложения капитала за рубеж прямой инвестор? Прямые инвестиции – это вложение денежн...