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.  

 

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

42736. Исследование трехфазного двигателя и однофазном и конденсаторном режимах 61 KB
  Ход работы: Теоретический материал: а Принцип работы однофазного АД основан на б Пусковой момент однофазного АД равен в Фаза смещающий элемент это аппарат предназначенный для г Пусковая емкость предназначена Рабочая емкость предназначена для д Рабочие свойства АД лучше в однофазном или конденсаторном режиме Ознакомиться с конструкцией трехфазного АД и записать паспортные данные. А...
42737. ИССЛЕДОВАНИЕ АНАЛОГОВЫХ КОМПАРАТОРОВ 76.5 KB
  При этом ОУ работает преимущественно в области положительного или отрицательного ограничения выходного напряжения проходя область усилительного режима только вблизи порога. Использование разных входов ОУ для подачи входного сигнала позволяет реализовать фиксацию уровня входного напряжения положительным или отрицательным перепадом напряжения на выходе компаратора.4 приведены схемы детекторов положительного и отрицательного уровней входного напряжения. Пороговый уровень входного напряжения в этих схемах задается величиной напряжения смещения...
42739. Линейный вычислительный процесс 241.5 KB
  Автомобиль в первый день проехал 24 намеченного пути во второй день – 46 пути а в третий – остальные 450 км. Используя операцию деления нацело найти количество полных метров в нем 1 метр = 100 см Вариант 2 Найти площадь треугольника по формуле Герона по заданным сторонам b c. Используя операцию деления нацело найти количество полных тонн в ней 1 тонна = 1000 кг Вариант 3 Три пассажира одновременно сели в такси.
42740. Разветвляющийся вычислительный процесс 208 KB
  Определить поместится ли квадрат в круге. Определить принадлежность заданной точки заштрихованной области включая ее границы. Определить есть ли среди них хотя бы одна пара одинаковых чисел. Определить принадлежность заданной точки заштрихованной области включая ее границы.
42742. Циклический вычислительный процесс 110 KB
  Составить математическую модель решения задач Задания 1 и Задания 2, нарисовать блок-схемы алгоритма, написать 3 программы на языке Паскаль (первая программа с использованием оператора цикла FOR, вторая – с использованием оператора WHILE, третья – с использованием оператора REPEAT). 2. Оформить в виде отчета (с.4).3. Ответить на контрольные вопросы (с.5). 4. Отчет представить преподавателю в распечатанном виде.
42743. Одномерные массивы 126 KB
  Размерность массива задать самостоятельно. Вариант Задачи 1 Заполнить массив случайными числами положительными и отрицательными из произвольного диапазона. Вывести созданный массив на экран расположив элементы в одну строку через пробелы.
42744. Разработка туристического продукта развлекательной тематики в гродненской области 476 KB
  раскрыть лексико-семантические и деривационные особенности молодежного сленга, отличающих его от других социолектов, а также его значимость как явления молодежной субкультуры второй половины ХХ–начала XXI вв...