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.  

 

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

12876. Развитие памяти и внимания у детей младшего школьного возраста 40 KB
  Уроктренинг по теме: Развитие памяти и внимания у детей младшего школьного возраста ЦЕЛИ ЗАНЯТИЯ: 1. Проверить уровень зрительной и слуховой памяти внимания.2. Начать работу по развитию произвольной памяти и внимания у детей младшего школьного возраста.3. Показать д...
12877. Развитие эмоциональной волевой сферы средствами арт-терапии 92 KB
  Коррекционноразвивающая программа: Развитие эмоциональной волевой сферы средствами арттерапиидля работы с дезадаптированными детьми 7 8 лет Пояснительная записка Проблема адаптации первоклассника к обучению в школе является одной из важных для психологии образо...
12878. ПРАКТИЧЕСКИЙ КУРС «В ПОИСКАХ СВОЕГО ПРИЗВАНИЯ» 75.37 KB
  ПРАКТИЧЕСКИЙ КУРС В ПОИСКАХ СВОЕГО ПРИЗВАНИЯ ВВЕДЕНИЕ Методический материал программа практических занятий со старшеклассниками по курсу В поисках своего призвания представляет собой конспекты уроков написанные в виде сценариев и допускающие возможность ...
12879. Биологические ритмы и их влияние на здоровье 77 KB
  Урок валеологии: Биологические ритмы и их влияние на здоровье Цели: ознакомить учащихся с новым понятием – биоритмы суточные недельные месячные сезонные; рассмотреть каким образом биоритмы влияют на здоровье человека его работоспособность; с помощью анкеты ...
12880. ГОЛОС ЧУЖОЙ ПЛАНЕТЫ 71 KB
  ГОЛОС ЧУЖОЙ ПЛАНЕТЫ Вашему вниманию предлагается иградрама. Мы играли в нее не только со старшеклассниками но и с педагогами представителями администрации психологами. Игра эта сложная как для проводящих ее так и для игроков. Она предполагает создание ситуации в...
12881. ПУТЕШЕСТВИЕ К ВОЛШЕБНИКУ 96.5 KB
  ПУТЕШЕСТВИЕ К ВОЛШЕБНИКУ Предлагаемую ниже игру можно использовать и как самостоятельную процедуру и в рамках психологического тренинга для подростков. В последнем случае игра встраивается в программу тренинга в форме отдельного занятия в котором представлены все...
12882. Психологическая игра Война племен 37.5 KB
  Психологическая игра Война племен Цель: развитие внутригрупповых отношений; навыков коллективного взаимодействия снятие агрессии. Участники игры: учащиеся 68 классов. Время проведения занятия: 1час 30 мин. Предполагаемый психологический результат: улучшение взаи...
12883. Дороги, которые мы выбираем. Сценарий мероприятия по актуальным проблемам подросткового возраста 41 KB
  Сценарий мероприятия по актуальным проблемам подросткового возраста Дороги которые мы выбираем... В конкурсе принимают участие ученики 9 11го класса. Соревнуются 2 команды по 12 человек. Члены команды: капитан; прессцентр 2 чел.; выездная бригада 3чел.; члены команд
12884. Здоровье и моя будущая профессия 41 KB
  Здоровьесберегающие технологии в воспитании и развитии детей. Круглый стол Здоровье и моя будущая профессия Программное содержание. Учить детей снимать эмоциональное и физическое напряжение преодолевать чувство тревоги связанное с межличностным общением. Форм...