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.  

 

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

80303. Цивільно-правовий захист права інтелектуальної власності 127.5 KB
  Цивільноправовий захист права інтелектуальної власності. Загальні положення про цивільноправовий захист права інтелектуальної власності. Правопорушення у сфері інтелектуальної власності їх особливості. Проблемні питання цивільноправового захисту авторських прав.
80305. Корпоративні права держави 118 KB
  Корпоративні права держави Поняття корпоративних прав. Загальні засади здійснення корпоративних прав держави та управління ними. Повноваження державних органів щодо управління корпоративними правами держави. Критерії ефективності управління корпоративними правами держави.
80306. Проблеми цивільно-правового регулювання особистих немайнових прав фізичної особи та їх захисту 155.5 KB
  Особисті немайнові права що забезпечують природне існування фізичної особи. а Особливості реалізації та цивільноправового захисту права на медичну допомогу. Проблеми реалізації права на опіку або піклування. Особисті немайнові права що забезпечують соціальне буття фізичної особи.
80307. Проблеми недійсності правочинів 369.5 KB
  Правові наслідки вчинення правочину всупереч вимогам закону. Правові наслідки недійсності правочину. Шахматовим було введено у юридичну лексику поняття модель протиправного правочину яке заслуговує на його подальше використання. Моделлю протиправного правочину В.
80309. Оплата праці на підприємстві 126.5 KB
  Мотивація - це процес формування в людини або групи людей мотивів до діяльності, спрямованої на досягнення індивідуальних і загальних цілей організації, підприємства.
80310. Витрати виробництва і собівартість продукції підприємства 199.5 KB
  Для визначення витрат на підприємстві використовується термін собівартість продукції до якої зараховують поточні витрати на її виробництво та збут виражені у грошовій формі. Витрати підприємства відшкодовуються за рахунок двох власних джерел: собівартості та прибутку. Усі витрати що формують собівартість продукції можна класифікувати за певними ознаками табл.
80311. Ціни та ціноутворення в ринкових умовах 449.5 KB
  Ціни у діяльності промислового підприємства виконують три основні функції: облікововимірювальну стимулюючу розподільчу. Облікововимірювальна функція ціни є засобом обліку й вимірювання витрат суспільної праці на виробництво окремих видів промислової продукції або надання відповідних послуг. Стимулюючу функцію ціни використовують для мотивації підвищення ефективності підприємницької діяльності забезпечення необхідної прибутковості дохідності кожному з учасників процесу товарообміну.