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

Содержание слайда: Лекция 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. Задача линейного программирования Это стандартная форма записи

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

Содержание слайда: 3.2. ЗЛП может: не иметь ни одного оптимального решения допустимой области не существует – система ограничений не совместна 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

Содержание слайда: 3.2. z = max(x1+x2|0.1x1+0.2x2  5, x1  0, x2  0) x1=50, x2 =0; z = 50

Содержание слайда: 3.2. 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

Содержание слайда: 3.2. z = max(x1+x2|x1+5x2  1, x1+x2  5, x1  0, x2  0)

Содержание слайда: 3.2. z = max(2x1+x2|0.1x1+0.1x2  5, x1  0, x2  0)

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

Содержание слайда: 3.3. z = max(x1+x2|0.1x1+0.2x2  5, x1–2x2  75, x1  0, x2  0) x1=50, x2 =0; z = 50 Каноническая форма: max x1+x2 0.1x1+0.2x2+x3 = 5 x1–2x2 +x4 = 75 x1  0, x2  0, x3  0, x4  0

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

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

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

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

Содержание слайда: 3.4. Экономические приложения линейного программирования

Содержание слайда: 3.4. Экономические приложения линейного программирования

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

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