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

вузов / Под ред. В.В. Федосеева. — 2-е изд.

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

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

предполагает следующее:
наличие определённых ресурсов
наличие определённых технологических возможностей
цель хозяйственной деятельности
извлечение

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

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

функция
Линейные ограни-чения

Условия неотрицательности переменных
Применение линейного программирования в математических моделях ©

Н.М. Светлов, 2007-2011

функция
Линейные ограни-чения
Условия неотрицательности переменных
Любую ЗЛП можно записать в каноническом

виде (ограничения – равенства, свободные члены неотрицательны, решается на максимум)

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

канонической форме
Линейная целевая функция
Линейные ограни-чения
Условия неотрицательности переменных
Применение линейного программирования

в математических моделях © Н.М. Светлов, 2007-2011

функция
Линейные ограни-чения
Условия неотрицательности переменных
Применение линейного программирования в математических моделях ©

Н.М. Светлов, 2007-2011

(безотносительно к целевой функции), называется допустимым решением
Если допустимых решений

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

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

не существует – система ограничений не совместна
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

Компактная запись

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

x2 ≥ 0)
x1=50, x2 =0; z = 50

Применение

линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

x2 ≥ 0)
x1=50, x2 =0; z = 50

… x1=0, x2 =50; z = 50

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

x1 ≥ 0, x2 ≥ 0)
Несовместность системы ограничений
Применение линейного

программирования в математических моделях © Н.М. Светлов, 2007-2011

x2 ≥ 0)
Неограниченность целевой функции
Применение линейного программирования в математических

моделях © Н.М. Светлов, 2007-2011

в канонической форме
Её ограничения линейно независимы
Известно опорное решение, в

котором:
имеется не более m ненулевых переменных
задача содержит n переменных и m ограничений
все ограничения выполняются
m переменных, называемых базисными (среди которых все ненулевые)
выражены через:
n–m переменных, называемых свободными (каждая равна нулю)
свободный член ограничения
Результат этой процедуры записан в начальную (первую, исходную) симплексную таблицу

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

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

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

cj нет, достигнут оптимум
Разрешающая строка:
для всех положительных aij в

выбранном столбце считаем bi /aij
если положительных нет, ц.ф. не ограничена
выбираем строку, где это значение минимально

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

i ≠i' : aijнов = aij – ai'jaij' /ai'j'

, где
i' и j' – координаты выбранных (разрешающих) строки и столбца
для строки i =i' : aijнов = aij /ai'j'

Положительных cj больше нет – достигнут оптимум (в больших задачах для этого требуются тысячи итераций)

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

произвольный набор базисных переменных и выражаем их через свободные
Если

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

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

преодоления этой проблемы описаны в рекомендуемой литературе.
Применение линейного программирования

в математических моделях © Н.М. Светлов, 2007-2011

для обеспечения единичного объёма производства в каждой отрасли.

Строки –

ресурсы, столбцы – отрасли.

Объёмы невоспроизводимых ресурсов (земельные угодья, трудовые ресурсы, запасы полезных ископаемых и т.п.), имеющиеся в распоряжении народного хозяйства

Матрица затрат (+) и выпуска (-) ресурсов при единичном объёме производства в каждой отрасли.

Строки – ресурсы, столбцы – отрасли.

Вектор, состоящий из нулей

Матрица выпуска (+) конечной продукции при единичном объёме производства в каждой отрасли.

Строки – виды продукции, столбцы – отрасли.

Вектор объёмов потребления каждого вида конечной продукции при единичном (стандартном) уровне удовлетворения потребностей

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

вычетом НДС), руб./ед.
Вектор цен ресурсов (включая НДС), руб./ед.
Матрица затрат

ресурсов на производство и реализацию единицы продукции, ед.рес./ед.прод.

Вектор наличия (начальных запасов) ресурсов

Матрица объёмов обязательств, выполняемых вследствие реализации единицы продукции каждого вида

Объёмы обязательств, имеющихся у предприятия и учитываемых при оптимальном планировании (выполнение которых зависит от составленного плана)

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

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








Запуск решения – [Ctrl]+[x]
Найти XA