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.  

 

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

30588. Личность журналиста в системе журналистики 31 KB
  Личность журналиста в системе журналистики. то же самое в вопросе № 49: индивидуальные характеристики творческой личности Творческая индивидуальность журналиста особое качество личности которое она приобретает и выявляет в конкретном виде данной деятельности Компоненты творческой индивидуальности: Знания общекультурные и профессиональные Умения опыт самостоятельный творческий подход Желания журналиста его потребности: мотивы интерес желания страсть внешние материальные и духовные внутренние. Мотивация журналиста:...
30589. Диалог как основа творчества 30.5 KB
  Диалог как основа творчества. Познание ограничивается самим собой и лишь диалог как форма предполагающая активную деятельность выводит на орбиту социального. Диалог как точно подметил Л. Диалогизм ваейшая черта человеческого бытия.
30590. Ассоциативность мышления журналиста 14.14 KB
  Ассоциация проявляется в метафоре. Эпитет весны здесь выступает и как ассоциация. Ассоциация должна быть яркой и жизненной.а Ассоциация является одним из составляющих творческого начала.
30591. Фантазия, воображение в творчестве журналиста 15.08 KB
  Фантазия воображение в творчестве журналиста.Фантазия и воображение широко используются в творчестве журналиста. Фантазия и воображение являются для журналиста одновременно и помощником и неприятелем. Воображение позволяет представить результат труда до его начала тем самым ориентируя журналиста в процессе творческой деятельности.
30592. Отражение в творчетстве журналиста 13.92 KB
  Отражение в творчетстве журналиста. На уровне организма отражение первично проявляется в раздражимости как возникающей под воздействием внешних и внутренних стимулов способности живой материи отвечать на воздействие избирательной реакцией соответствующей особенностям источника. Такое отражение в процессе развития преобразуется в чувствительность как способность иметь ощущения первичные психические образы среды. Отражение служит предпосылкой развития более сложных форм.
30593. Эмоциональная и реальное в журналистике 14.05 KB
  Эмоции психическое отражение в форме непосредственного пристрастного переживания жизненного смысла явлений и ситуаций обусловленного отношением их объективных свойств к потребностям субъекта.Простейшая форма эмоции т. Эмоции в творчестве выражают оценки явлениям событиям. Трудно представить себе репортаж без эмоции.
30594. Проявление эстетической активности в безобразном и трагическом 14 KB
  Но само изображение жука привлекает нас силой эстетического воздействия. Художественное изображение привлекает внимание именно как эстетически организованное изображение.Проявления комического безобразного трагического в реальной действительности лишь тогда становятся эстетическими реальностями когда они переходя в художественное изображение приобретают тем самым эстетическую организованность и начинают действовать уже не только как бытовые проявления комического безобразного и трагического но и художественного т.
30595. Проявление эстетической активности и релейная функция художественных средств 52 KB
  Еще Аристотель писал о том что явление ктр в действительности вызывает в нас отвращение будучи художественно изображенным привлекает нас но в то же время сам по себе объект изображения не делается от этого менее отвратительным Так рисунок жука большого неуклюжего Дюрера производит отталкивающее впечатление. ОТ ФАКТА К ДОКУМЕНТАЛЬНОМУ ОБРАЗУ В ХУДОЖЕСТВЕННОПУБЛИЦИСТИЧЕСКИХ ЖАНРАХ обозрение очерк фельетон памфлет Этой группе публицистики свойственны образность типизация насыщенность литературнохудожественными изобразительными...
30596. Информация сигнала и природа красоты 34 KB
  Информация сигнала и природа красоты Сигнал его природа и действенность Сигнал это импульс приводящий в действие те или иные системы. Сигнальная активность красоты В природе и взаимодействии живых существ сигнальноорганизующие действия имеют большое значение. творить по законам красоты. Бескорыстность красоты Смысл действия красоты не в том что мы чето имеем с нее а в том что образ красивого объекта проникает в структуру чувств и организует их.