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.  

 

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

58509. Новогодняя открытка 47.5 KB
  После смерти Петра I новогодние елки ставить перестали. Лишь владельцы трактиров украшали ими свои дома причем эти елки стояли на трактирах круглый год отсюда пошло их название елки-палки. Новогодние празднества и традиция ставить елки возродились при Екатерине II.
58510. Понятие информации. Виды информации. Свойства информации 62.5 KB
  Цель урока: Познакомить учащихся с понятием информации и носителями информации. Учащиеся должны понимать, что существуют различные подходы к определению информации в различных областях человеческой деятельности...
58511. Поняття алгоритму. Базові структури алгоритмів 163 KB
  Виконання алгоритму повинно приводити до очікуваного результату за скінченну кількість кроків. Виконання алгоритму завжди повинно призводити до певного результату. Виконавець відповідно до алгоритму повинен одержати результат не вникаючи в його суть.
58512. Проведення реєстрації осіб, які виявили бажання пройти зовнішнє незалежне оцінювання в 2012 році. Робота з програмою створення заяви-реєстраційної картки 166 KB
  Мета уроку: ознайомити учнів з порядком реєстрації на зовнішнє незалежне оцінювання 2012 року навчити учнів користуватися програмою реєстрації на ЗНО 2012 ознайомити учнів з правами та обов’язками осіб які бажають взяти участь у ЗНО...
58513. Властивості інформації. Кодування інформації 82.5 KB
  Перевірка домашнього завдання 67 хв. Зараз я пройду та перевірю домашнє завдання. 1 учень: Запиши у якому вигляді подано інформацію в таких прикладах: Хто не виконав завдання слідкуйте і самостійно запишіть відповідь у таблицю.
58514. Первобытный мир – первые шаги человечества 153.5 KB
  Цели: образовательные: создать у детей образ эпохи Первобытного мира; проследить расселение первобытных людей по планете; развивающие: учить анализировать ответы товарищей и высказывать свое мнение; познакомить с открытиями и изобретениями древних людей...
58517. ВОЕННЫЕ ПОХОДЫ ФАРАОНОВ 33.5 KB
  ЗАДАЧИ: образовательные изучить причины характер и последствия военных походов фараонов Древнего Египта научить распознавать интересы различных общественных групп; развивающие продолжить формирование умений работать с исторической картой...