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.  

 

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

12004. Банковская система России. Анализ становления и тенденции развития 901.5 KB
  ТЕМА: Банковская система России. Анализ становления и тенденции развития Введение Интерес к ныне существующей в России банковской системе вызван как практическими так и теоретическими обстоятельствами. Известно что банковская система России прошла сложны...
12005. Становление и развитие кредитных организаций в Республике Казахстан 891.07 KB
  Современное состояние и анализ развития кредитных организаций в Республике Казахстан. Анализ деятельности банков как кредитных организаций. Динамика развития небанковских кредитных организаций в Казахстане. Оценка деятельности кредитного учреждения АО Астана-Финанс
12006. Совершенствование банковского надзора в республике Казахстан 599.85 KB
  Регулирование и надзор деятельности банков второго уровня Содержание Введение. Теоретические основы регулирования и надзора банковской деятельности. Цели принципы и задачи государственного регулирования и надзора банковской
12007. Товар и товарная политика в маркетинге 288.5 KB
  Сердцевиной деятельности любого предприятия является товар – сложное социально-экономическое понятие рыночной экономики. «Если у Вас нет товара, у Вас ничего нет» – гласит первая заповедь маркетинга. Товар– изделие, которое характеризуется тремя основными особенностями
12008. Дослідження теоретичних та методологічних основ державного регулювання грошового обороту України 93.28 KB
  Вивчення наявного теоретичного матеріалу з даної теми; проведення аналізу сучасного стану грошового обороту України; дослідження особливостей державного регулювання грошового обороту України; виказання основних напрямків удосконалення державного регулювання грошового обороту України.
12009. Анализ действующей практики осуществления кредитных операций коммерческих банков на примере ОАО Банк Центр Кредит 126.26 KB
  Содержание Введение І. Виды кредитов и их характеристика 1.1 Необходимость сущность и значение кредита 1.2 Классификация банковских кредитов ссуд 1.3 Организация банковского кредитования ІІ. Анализ действующей практики кредитования банками второго уровня ЗК н...
12010. Обобщение теоретической и правовой базы ипотечного кредитования под залог земель сельскохозяйственного назначения 716.06 KB
  ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ГЛАВА 1. Теоретические основы деятельности ипотечных банков в системе земельноипотечного кредитования предпринимательских структур аграрного сектора экономики 1.1 Ипотека: понятие сущность отличительные черты. Особенности земельной ипотек
12011. Система оценки финансового состояния деятельности коммерческого банка 454.94 KB
  СОДЕРЖАНИЕ Введение 1. Финансовое состояние коммерческого банка и организационнометодическое обеспечение его оценки 1.1 Финансовое состояние банка и факторы его определяющие 1.2 Организационные основы оценки финансового состояния банка 1.3 Направления оценки ф...