42063

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

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

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

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

Русский

2015-01-19

223 KB

29 чел.

Лабораторная работа 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.  

 

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

31633. ПАТОФІЗІОЛОГІЯ ПЕЧІНКИ 79.5 KB
  Це обумовлює характерну ознаку печінкової недостатності нестабільний рівень глюкози крові: 1 після прийому їжі розвивається гіперглікемія 2 натще гіпоглікемія. Таке явище супроводжується збільшенням в крові рівня вільного холестерину і зниженням антиатерогенних ліпопротеїнів що сприяє відкладенню холестерину в стінках судин і розвитку атеросклерозу. Порушення участі печінки в білковому обміні включає 3и групи змін: 1 зниження синтезу гепатоцитами альбумінів що веде до гіпоальбумінемії і гіпоонкії крові а на стадії...
31634. Система кодирования информации 19.55 KB
  Система кодирования информации Кодирование информации применяют для унификации формы представления данных которые относятся кразличным типам в целях автоматизации работы с информацией. Например естественные человеческие языки можно рассматривать как системы кодирования понятий для выражения мыслей посредством речи к тому же и азбуки представляют собой системы кодирования компонентов языка с помощью графических символов. Основой этой системы кодирования является представление данных через последовательность двух знаков: 0 и 1. Наименьшая...
31636. Положение слуховой трубы у взрослого и ребенка, связь ее с мышцами мягкого неба, значение для слуховой функции 14.62 KB
  Служит для доступа воздуха из глотки в барабанную полость, чем поддерживается равновесие между давлением в этой полости и внешним атмосферным давлением, что необходимо для правильного проведения к лабиринту колебаний барабанной перепонки.
31637. Накопители на гибких магнитных дисках 99 KB
  Структура накопителя на гибких магнитных дисках Устройство накопителя на гибких магнитных дисках НГМД рис. Все электрические схемы размещаются на печатной плате компонуемой в корпусе НГМД. Обычно в профессиональной ПЭВМ к одному адаптеру через интерфейс можно подключать до четырех НГМД. Для подключения определенных НГМД применяются микропереключатели.
31639. Накопители на оптических дисках 1.41 MB
  Основы оптической записи Методы оптической записи на поверхности подвижного носителя основаны на способности некоторых материалов изменять отражательные свойства на участках которые подвергались тепловому магнитному или комбинированному воздействию. Первоначально для оптической записи использовалось свойство лазерного луча прожигать отверстия в тонком слое металла рис. Такой способ записи используется для НОД с однократной записью. Возможность многократной записи обеспечивается при использовании магнитооптических носителей.
31640. Видеоадаптеры. Графические видеоадаптеры точечные 33.63 KB
  Последней командой графического файла является команда безусловного перехода на начало файла что обеспечивает регенерацию изображения. Структура графического адаптера с произвольным сканированием векторного типа: СМ сумматор ГВ генератор векторов Если адаптер работает в абсолютных координатах то ЦП сильно загружен в режиме редактирования или перемещения изображения. Адаптеры такого типа обладают отсутствием мерцания возможностью наложения изображения из видеоЗУ на стандартное телевизионное изображение от телекамеры или...
31641. Системные и локальные шины 23.51 KB
  Стоимость такой организации получается достаточно низкой поскольку для реализации множества путей передачи информации используется единственный набор линий шины разделяемый множеством устройств. Одна из причин больших трудностей возникающих при разработке шин заключается в том что максимальная скорость шины главным образом лимитируется физическими факторами: длиной шины и количеством подсоединяемых устройств и следовательно нагрузкой на шину. Эти физические ограничения не позволяют произвольно ускорять шины.