Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

/23ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. — глава 2.Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, 2001.Канторович Л.В. Экономический расчёт
/23Лекция 3. Применение линейного программирования в математических моделяхСодержание лекции:Принцип оптимальности в планировании /23ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. /233.1. Принцип оптимальности в планировании и управленииПринцип оптимальности предполагает следующее:наличие определённых ресурсовналичие /233.2. Задача линейного программированияЭто развёрнутая форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия неотрицательности переменныхПрименение /233.2. Задача линейного программированияЭто каноническая форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия неотрицательности переменныхЛюбую /233.2. Задача линейного программированияЭто матричная форма записиОна тождественна канонической формеЛинейная целевая функцияЛинейные /233.2. Задача линейного программированияЭто стандартная форма записиЛинейная целевая функцияЛинейные ограни-ченияУсловия неотрицательности переменныхПрименение /233.2.Любой вектор x, удовлетворяющий ограничениям и условиям неотрицательности (безотносительно к целевой функции), /233.2.ЗЛП может:не иметь ни одного оптимального решениядопустимой области не существует – система /233.2.z = max(x1+x2|0.1x1+0.2x2  5, x1  0, x2  0) x1=50, /233.2.z = max(x1+x2|0.1x1+0.1x2  5, x1  0, x2  0) x1=50, /233.2.z = max(x1+x2|x1+5x2  1, x1+x2  5, x1  0, x2 /233.2.z = max(2x1+x2|0.1x1+0.1x2  5, x1  0, x2  0)Неограниченность целевой /233.3. Симплексный методИсходные условия применения симплексного методаЗЛП записана в канонической формеЕё ограничения /233.3.z = max(x1+x2|0.1x1+0.2x2  5, x1–2x2  75,  x1  0, /23В таблице выделены жирным шрифтом3.3.Разрешающий столбец:столбец с наибольшим положительным cjесли положительного cj /233.3.Выполняем обыкновенные жордановы исключения во всей таблице:для строк i i' : aijнов /233.3.Опорное решение может быть получено по следующей процедуре:Выбираем произвольный набор базисных переменных /233.3.В некоторых случаях алгоритм симплексного метода может зацикливаться.Пути преодоления этой проблемы описаны /233.4. Экономические приложения линейного программированияМатрица потребности в ресурсах для обеспечения единичного объёма /233.4. Экономические приложения линейного программированияВектор цен продукции (за вычетом НДС), руб./ед.Вектор цен Применение линейного программирования в математических моделях (с) Н.М. Светлов, 2007/233.5. Программное обеспечение /233.5.Два способа установки XAЕсли есть права доступа к каталогу C:\WINDOWSкопируем туда файлы
Слайды презентации

Слайд 2 /23
Литература
Экономико-математические методы и прикладные модели: Учеб. пособие для

/23ЛитератураЭкономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под

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

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

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


Слайд 3 /23
3.1. Принцип оптимальности в планировании и управлении
Принцип оптимальности

/233.1. Принцип оптимальности в планировании и управленииПринцип оптимальности предполагает следующее:наличие определённых

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

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

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


Слайд 4 /23
3.2. Задача линейного программирования
Это развёрнутая форма записи
Линейная целевая

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

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

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

Слайд 5 /23
3.2. Задача линейного программирования
Это каноническая форма записи
Линейная целевая

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

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

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

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


Слайд 6 /23
3.2. Задача линейного программирования
Это матричная форма записи
Она тождественна

/233.2. Задача линейного программированияЭто матричная форма записиОна тождественна канонической формеЛинейная целевая

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

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

Слайд 7 /23
3.2. Задача линейного программирования
Это стандартная форма записи
Линейная целевая

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

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

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

Слайд 8 /23
3.2.
Любой вектор x, удовлетворяющий ограничениям и условиям неотрицательности

/233.2.Любой вектор x, удовлетворяющий ограничениям и условиям неотрицательности (безотносительно к целевой

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

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

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


Слайд 9 /23
3.2.
ЗЛП может:
не иметь ни одного оптимального решения
допустимой области

/233.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

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

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


Слайд 10 /23
3.2.
z = max(x1+x2|0.1x1+0.2x2  5, x1  0,

/233.2.z = max(x1+x2|0.1x1+0.2x2  5, x1  0, x2  0)

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

Применение

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

Слайд 11 /23
3.2.
z = max(x1+x2|0.1x1+0.1x2  5, x1  0,

/233.2.z = max(x1+x2|0.1x1+0.1x2  5, x1  0, x2  0)

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

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

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


Слайд 12 /23
3.2.
z = max(x1+x2|x1+5x2  1, x1+x2  5,

/233.2.z = max(x1+x2|x1+5x2  1, x1+x2  5, x1  0,

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

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

Слайд 13 /23
3.2.
z = max(2x1+x2|0.1x1+0.1x2  5, x1  0,

/233.2.z = max(2x1+x2|0.1x1+0.1x2  5, x1  0, x2  0)Неограниченность

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

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

Слайд 14 /23
3.3. Симплексный метод
Исходные условия применения симплексного метода
ЗЛП записана

/233.3. Симплексный методИсходные условия применения симплексного методаЗЛП записана в канонической формеЕё

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

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

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


Слайд 15 /23
3.3.
z = max(x1+x2|0.1x1+0.2x2  5, x1–2x2  75,

/233.3.z = max(x1+x2|0.1x1+0.2x2  5, x1–2x2  75, x1  0,

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


Слайд 16 /23
В таблице выделены жирным шрифтом
3.3.
Разрешающий столбец:
столбец с наибольшим положительным cj
если положительного

/23В таблице выделены жирным шрифтом3.3.Разрешающий столбец:столбец с наибольшим положительным cjесли положительного

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

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

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


Слайд 17 /23
3.3.
Выполняем обыкновенные жордановы исключения во всей таблице:
для строк

/233.3.Выполняем обыкновенные жордановы исключения во всей таблице:для строк i i' :

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

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

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

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


Слайд 18 /23
3.3.
Опорное решение может быть получено по следующей процедуре:

Выбираем

/233.3.Опорное решение может быть получено по следующей процедуре:Выбираем произвольный набор базисных

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

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

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


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

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

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

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

Слайд 20 /23
3.4. Экономические приложения линейного программирования
Матрица потребности в ресурсах

/233.4. Экономические приложения линейного программированияМатрица потребности в ресурсах для обеспечения единичного

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

Строки –

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

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

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

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

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

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

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

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

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


Слайд 21 /23
3.4. Экономические приложения линейного программирования
Вектор цен продукции (за

/233.4. Экономические приложения линейного программированияВектор цен продукции (за вычетом НДС), руб./ед.Вектор

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

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

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

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

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

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


Слайд 22 Применение линейного программирования в математических моделях (с) Н.М. Светлов,

Применение линейного программирования в математических моделях (с) Н.М. Светлов, 2007/233.5. Программное

2007
/23
3.5. Программное обеспечение линейного программирования
Запуск решения – [Ctrl]+[x]
Найти XA


  • Имя файла: primenenie-lineynogo-programmirovaniya-v-matematicheskih-modelyah.pptx
  • Количество просмотров: 105
  • Количество скачиваний: 0
- Предыдущая Торговая мебель