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.  

 

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

18278. ВІДНОШЕННЯ НА МНОЖИНІ 121.5 KB
  Лекція 5 ВІДНОШЕННЯ НА МНОЖИНІ Відношення на множині та його основні характеристики. Особливості графа відношення на множині. Способи задання відношень на множині. Основні властивості відношень на множині: рефлективність і антирефлексивність симетричність ...
18279. ФУНКЦІЇ ВІДОБРАЖЕННЯ 260.5 KB
  Лекція 6 ФУНКЦІЇ ВІДОБРАЖЕННЯ Поняття функції та її основні характеристики. Способи задання функцій. Відображення і їх види. Рівнопотужні множини. Потужність множини. Теорема про обєднання рівно потужних множин. Питання на самостійне опрацю
18280. АЛГЕБРАЇЧНІ ОПЕРАЦІЇ І АЛГОРИТМИ 72.5 KB
  Лекція 7 АЛГЕБРАЇЧНІ ОПЕРАЦІЇ І АЛГОРИТМИ Бінарні алгебраїчні операції та їх основні характеристики. Асоціативний і комутативний закони операції. Дистрибутивні закони що повязують дві операції. Операція обернена даній. Питання на самостійне опр...
18281. ЛОГІКА ВИСЛОВЛЕНЬ 143.5 KB
  Лекція 8 ЛОГІКА ВИСЛОВЛЕНЬ Поняття про твердження. Математичні твердження та їх види. Висловлювання логічне значення висловлення. Логічні сталі. Прості і складні висловлення. Пропозиційні змінні. Операції заперечення конюнкції дизюнкції та еквіва
18282. ЛОГІКА ПРЕДИКАТІВ 172.5 KB
  Лекція 9 ЛОГІКА ПРЕДИКАТІВ Поняття про зміну в математиці. Предикат висловлювальна форма та його основні характеристики. Тотожно істинні тотожно хибні і рівносильні предикати. Операції логіки висловлень над предикатами. Області істинності результат
18283. МІРКУВАННЯ ТА ПЕРЕВІРКА ЇХ ПРАВИЛЬНОСТІ 87.5 KB
  Лекція 10 МІРКУВАННЯ ТА ПЕРЕВІРКА ЇХ ПРАВИЛЬНОСТІ Поняття про міркування. Правильні і неправильні міркування. Перевірка правильності міркувань за допомогою кругів Ейлера або наведення контрприкладу. Теореми і їх будова. Твердження що повязані з даною те
18284. РІЗНІ ПІДХОДИ ДО ПОБУДОВИ МНОЖИНИ ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ 70 KB
  Лекція 11 РІЗНІ ПІДХОДИ ДО ПОБУДОВИ МНОЖИНИ ЦІЛИХ НЕВІДЄМНИХ ЧИСЕЛ Короткі історичні відомості про виникнення натурального числа і нуля. Різні підходи до побудови множини цілих невідємних чисел. Скінченні множини та їх властивості: а Теоретикомн
18285. МНОЖИНА ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ 53.5 KB
  Лекція 12 МНОЖИНА ЦІЛИХ НЕВІДЄМНИХ ЧИСЕЛ Натуральне число як спільна властивість класу скінченних непорожніх рівнопотужних множин. Поняття про нуль. Множина цілих невідємних чисел. Відношення рівності€ на множині цілих невідємних чисел та його властив
18286. ДОДАВАННЯ І ВІДНІМАННЯ ЦІЛИХ НЕВІД’ЄМНИХ ЧИСЕЛ 74 KB
  Лекція 13 ДОДАВАННЯ І ВІДНІМАННЯ ЦІЛИХ НЕВІДЄМНИХ ЧИСЕЛ Означення суми цілих невідємних чисел через обєднання множин. Існування і єдність суми. Операція додавання цілих невідємних чисел та їх властивості. Формування понять суми і додавання в початкові...