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.  

 

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

45334. Система законодательных (представительных) и исполнительных органов государственной власти субъектов Российской Федерации 20.8 KB
  Система законодательных представительных и исполнительных органов государственной власти субъектов Российской Федерации устанавливается ими самостоятельно в соответствии с основами конституционного строя Российской Федерации и ФЗ от 06. Об общих принципах организации законодательных представительных и исполнительных органов государственной власти субъектов Российской Федерации.Образование формирование деятельность законодательных представительных и исполнительных органов государственной власти субъектов Российской Федерации их...
45335. Законодательный процесс в РФ 25.93 KB
  В составе городского поселения также могут находиться сельские населенные пункты не имеющие статуса сельских поселений в которых местное самоуправление осуществляется населением непосредственно и или через выборные и иные органы местного самоуправления. Городской округ городское поселение которое не входит в состав муниципального района и органы местного самоуправления которого осуществляют полномочия по решению установленных законом вопросов местного значения поселения и вопросов местного значения муниципального района а также могут...
45336. Подходы к построению систем искусственного интеллекта 33 KB
  Структурный подход Под структурным подходом подразумевается попытки построить искусственный интеллект путём моделирования структуры человеческого мозга. Основной моделируемой структурной единицей в персептронах как и в большинстве других вариантов моделирования мозга является нейрон. Позднее возникли и другие модели которые обычно называют нейронные сети . Эти модели различаются по строению отдельных нейронов по топологии связей между ними и по алгоритмам обучения.
45337. Понятие дерева возможностей 36.5 KB
  Дерево быстро разрастается рис.1 Дерево возможных продолжений шахматной игры Все вершины могут быть двух типов. Таким образом дерево возможностей представляет собой чередующиеся слои альфа и бетавершин. Если бы дерево можно было обследовать полностью т.
45338. Основные понятия искусственного интеллекта 40 KB
  Интеллектом называется способность мозга решать задачи путём приобретения запоминания и целенаправленного преобразования знаний в процессе обучения на опыте и адаптации к разнообразным обстоятельствам. Искусственный интеллект это одно из направлений информатики целью которого является разработка аппаратнопрограммных средств позволяющих пользователюнепрограммисту ставить и решать свои традиционно считающиеся интеллектуальными задачи общаясь с компьютером на ограниченном подмножестве естественного языка. Понятие интеллектуальной задачи...
45339. Знания как часть любой интеллектуальной системы 38 KB
  При этом возникает естественный вопрос что такое знания и чем они отличаются от обычных данных обрабатываемых компьютером. Знания являются более сложной категорией информации по сравнению с данными. Они описывают не только отдельные факты но и взаимосвязи между ними поэтому знания иногда называют структурированными данными.
45340. Проблемная область искусственного интеллекта 35 KB
  Для этого разрабатываются специальные модели представления знаний и языки для описания знаний выделяются различные типы знаний. Изучаются источники из которых система может брать знания и создаются процедуры и приёмы с помощью которых возможно приобретение знаний интеллектуальными системами. Проблема представления знаний в системах искусственного интеллекта чрезвычайно актуальна поскольку функционирование данных систем опирается на знания о проблемной области хранящиеся на компьютере.
45341. Проблема распознавания образов 67.5 KB
  В своей повседневной жизни человек настолько легко справляется с задачами распознавания что это считается само собой разумеющимся. В целом проблема распознавания образов состоит из двух частей: обучения и распознавания. За обучением следует процесс распознавания новых объектов который характеризует действия уже обученной системы.
45342. Проблемы и перспективы нейронных сетей 48 KB
  Проблемы интерпретируемости приводят к снижению ценности полученных результатов работы сети а проблема размерности к очень жестким ограничениям на количество выходных нейронов в сети на количество рецепторов и на сложность структуры взаимосвязей нейронов с сети. уже сегодня искусственные нейронные сети используются во многих областях но прежде чем их можно будет применять там где на карту поставлены человеческие жизни или значительные материальные ресурсы должны быть решены важные вопросы касающиеся надежности их работы. Некоторые...