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.  

 

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

67988. Иван Владимирович Тюрин 132.5 KB
  Официальная биография говорит, что Иван Владимирович Тюрин родился 3 ноября 1892 году в селе Верхние Юшады Мензелинского района Уфимской области. Однако по воспоминаниям М. Оберландер, дочери И.В. Тюрина, в этом селе его крестили, а родился Иван Владимирович в доме своих родителей, Владимира Ивановича и Анастасии Васильевны...
67989. Определение концентрации Ge в эпитаксиальных пленках SixGe1-x/Si методом Оже-спектроскопии 749 KB
  Данное пособие подготовлено в рамках работ по проекту «Научно-образовательный центр Физика твердотельных наноструктур Нижегородского государственного университета им. Н.И.Лобачевского» Российско-американской программы «Фундаментальные исследования и высшее образование».
67990. Розвиток освіти в Іспанії 164.5 KB
  Перші школи в Іспанії як і в ін. школи для бідних а також ряд шкіл і колегіумів при інститутах створених педагогамигуманістами. Працюючим були доступні лише початкові школи але їх не вистачало. Незважаючи на те відповідно до конституції 1931 і закону 1933 школи релігійних організацій...
67991. Навчання в Росії в 11-14 століттях 116.5 KB
  Історичні зведення про російські школи убогі. Аж до XVІІ століття, коли святитель Дмитрій Ростовський влаштував перші народні школи. Істотно те, що характер народної освіти в Руській державі споконвічно складається як церковний і сімейний. Церковним було мистецтво, зачинателем якого став...
67992. Освітня справа доби гетьманату (квітень — грудень 1918 року) 138 KB
  Щоб зрозуміти погляд П. Скоропадського на державу, треба пояснити, у якому середовищі формувався світогляд гетьмана і в якому контексті доводилося йому діяти. Насамперед він був глибоко пов’язаний з історичною традицією. П. Скоропадський належав до старого козацького роду, серед якого був...
67993. Історичні умови, освіта і наука в період українського культурного відродження ХIХ століття 60.5 KB
  У кінці XVIII ст. територія України була розділена між Австрійською (увійшло 20% площі) і Російською (80%) імперіями. До цього часу завершилася ліквідація української державності. В обох імперіях розгалужений бюрократичний апарат повністю контролював всі сторони життя суспільства.
67994. РОЗВИТОК ШКОЛИ Й ПЕДАГОГІЧНОЇ ДУМКИ НА БУКОВИНІ 129.5 KB
  Еволюція українського шкільництва й педагогічної думки Буковини протікала в загальнонаціональному руслі історії України й належить до цінних надбань виховної культури українського народу. Тим більше, що на цій предковічній території з давніх часів жили українські племена, переважно тиверці та уличі.
67995. Основные физические и логические параметры жестких дисков 23.33 KB
  Все накопители так или иначе соответствуют стандартам, определяемым либо независимыми комитетами и группами стандартизации, либо самими производителями. Среди множества технических характеристик отличающих одну модель от другой можно выделить некоторые, наиболее важные с точки зрения...