Презентация на тему: Применение линейного программирования в математических моделях

Лекция 3. Применение линейного программирования в математических моделях Содержание лекции:Принцип оптимальности в планировании и управленииЗадача линейного программированияСимплексный методЭкономические приложения линейного программированияПрограммное обеспечение линейного программирования

Литература Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. — глава 2.Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, 2001.Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: Изд-во АН СССР, 1960.Светлов Н.М., Светлова Г.Н. Построение и решение оптимизационных моделей средствами программ MS Excel и XA: Методические указания для студентов экономического факультета / РГАУ – МСХА имени К.А. Тимирязева. М., 2005. http://svetlov.timacad.ru/umk1/xa_1.doc

3.1. Принцип оптимальности в планировании и управлении Принцип оптимальности предполагает следующее:наличие определённых ресурсовналичие определённых технологических возможностейцель хозяйственной деятельностиизвлечение прибылиудовлетворение потребностейпредотвращение угрозынакопление знанийи т.д.Суть принципа:планировать хозяйственную деятельность таким образом, чтобы при имеющихся ресурсах и технологиях не существовало способа достичь цели в большей степени, чем это предусматривает планВ полной мере этот принцип может быть реализован только с помощью экономико-математических моделей

3.2. Задача линейного программирования Линейная целевая функция Линейные ограни-чения Линейные ограни-чения Это развёрнутая форма записи

3.2. Задача линейного программирования Линейная целевая функция Линейные ограни-чения Условия неотрицательности переменных Любую ЗЛП можно записать в каноническом виде (ограничения – равенства, свободные члены неотрицательны, решается на максимум) Это каноническая форма записи

3.2. Задача линейного программирования Линейная целевая функция Линейные ограни-чения Условия неотрицательности переменных Это матричная форма записиОна тождественна канонической форме

3.2. Задача линейного программирования Линейная целевая функция Линейные ограни-чения Условия неотрицательности переменных Это стандартная форма записи

Любой вектор x, удовлетворяющий ограничениям и условиям неотрицательности (безотносительно к целевой функции), называется допустимым решениемЕсли допустимых решений не существует, говорят, что система ограничений несовместнаОбластью допустимых решений (ОДР) называется множество, включающее все допустимые решения данной ЗЛПДопустимое решение x*, доставляющее наибольшее значение целевой функции среди всех допустимых решений данной ЗЛП, называется оптимальным решениемчасто его называют просто решением ЗЛП

ЗЛП может:не иметь ни одного оптимального решениядопустимой области не существует – система ограничений не совместнаz = max(x1+x2|x1+5x2 1, x1+x2 5, x1 0, x2 0)допустимая область существует, но не ограничивает целевую функциюz = max(2x1+x2|0.1x1+0.1x2 5, x1 0, x2 0)иметь одно оптимальное решениеz = max(x1+x2|0.1x1+0.2x2 5, x1 0, x2 0) x1=50, x2 =0; z = 50иметь бесконечно много оптимальных решенийz = max(x1+x2|0.1x1+0.1x2 5, x1 0, x2 0) x1=50, x2 =0; z = 50 … x1=0, x2 =50; z = 50

z = max(x1+x2|0.1x1+0.2x2 5, x1 0, x2 0) x1=50, x2 =0; z = 50

z = max(x1+x2|0.1x1+0.1x2 5, x1 0, x2 0) x1=50, x2 =0; z = 50 … x1=0, x2 =50; z = 50

z = max(x1+x2|x1+5x2 1, x1+x2 5, x1 0, x2 0) Несовместность системы ограничений

z = max(2x1+x2|0.1x1+0.1x2 5, x1 0, x2 0) Неограниченность целевой функции

3.3. Симплексный метод Исходные условия применения симплексного методаЗЛП записана в канонической формеЕё ограничения линейно независимыИзвестно опорное решение, в котором: имеется не более m ненулевых переменныхзадача содержит n переменных и m ограниченийвсе ограничения выполняются m переменных, называемых базисными (среди которых все ненулевые)выражены через:n–m переменных, называемых свободными (каждая равна нулю)свободный член ограниченияРезультат этой процедуры записан в начальную (первую, исходную) симплексную таблицу

z = max(x1+x2|0.1x1+0.2x2 5, x1–2x2 75, x1 0, x2 0) x1=50, x2 =0; z = 50Каноническая форма:max x1+x20.1x1+0.2x2+x3 = 5x1–2x2 +x4 = 75x1 0, x2 0, x3 0, x4 0

Разрешающий столбец:столбец с наибольшим положительным cjесли положительного cj нет, достигнут оптимумРазрешающая строка:для всех положительных aij в выбранном столбцесчитаем bi /aijесли положительных нет, ц.ф. не ограниченавыбираем строку, где это значение минимально

Выполняем обыкновенные жордановы исключения во всей таблице:для строк i i' : aijнов = aij – ai'jaij' /ai'j' , гдеi' и j' – координаты выбранных (разрешающих) строки и столбцадля строки i =i' : aijнов = aij /ai'j' Положительных cj больше нет – достигнут оптимум (в больших задачах для этого требуются тысячи итераций)

Опорное решение может быть получено по следующей процедуре:Выбираем произвольный набор базисных переменных и выражаем их через свободныеЕсли строк с отрицательными свободными членами нет – опорное решение получено; иначе – п.3.Одну из таких строк выбираем в качестве вспомогательной целевой функции и проводим по ней процедуру решения на минимум, используя алгоритм симплекс-методаЕсли в качестве разрешающей выбирается строка с отрицательным свободным членом, то разрешающий элемент тоже должен быть отрицательнымдля всех aij в выбранном столбце считаем bi /aijнаименьшее положительное значение этого отношения указывает разрешающую строкуесли положительных нет, выбираем другую строку с отрицательным свободным членом в качестве вспомогательной целевой функцииесли таковых не находится, опорных решений не существует (целевая функция не ограничена множеством допустимых решений)Если оптимум достигнут при отрицательном свободном члене – система ограничений несовместна; иначе – п.5Как только достигнуто положительное значение свободного члена, переходим к п.2.

В некоторых случаях алгоритм симплексного метода может зацикливаться.Пути преодоления этой проблемы описаны в рекомендуемой литературе.

3.4. Экономические приложения линейного программирования Матрица потребности в ресурсах для обеспечения единичного объёма производства в каждой отрасли.Строки – ресурсы, столбцы – отрасли. Вектор объёмов потребления каждого вида конечной продукции при единичном (стандартном) уровне удовлетворения потребностей Матрица затрат (+) и выпуска (-) ресурсов при единичном объёме производства в каждой отрасли.Строки – ресурсы, столбцы – отрасли.

3.4. Экономические приложения линейного программирования Вектор цен продукции (за вычетом НДС), руб./ед. Объёмы обязательств, имеющихся у предприятия и учитываемых при оптимальном планировании (выполнение которых зависит от составленного плана)

3.5. Программное обеспечение линейного программирования

Два способа установки XAЕсли есть права доступа к каталогу C:\WINDOWSкопируем туда файлы CXA32.DLL и CAXA32.DLLИначекопируем файлы CXA32.DLL и CAXA32.DLL в ту папку, в которой решаем модельпосле вызова файла модели нажимаем кнопкуи указываем расположение любого из этих файловэто действие повторяется при каждом вызове ExcelАнтивирус Касперского блокирует выполнение XAПри первом вызове программы следует в ответ на предупреждение антивируса дать ему указание разрешать выполнение данной программы