Что такое 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
  • Количество просмотров: 156
  • Количество скачиваний: 0
- Предыдущая Открытки к 23 февраля
Следующая - Забавы по И. А. Крылову

Похожие презентации

Работа со шрифтами Работа со шрифтами 131
Презентация по информатике Работа с текстом WordArt Презентация по информатике Работа с текстом WordArt 166
Ақиқат кестеслері (жалған, ақықат), (8-сынып) Ақиқат кестеслері (жалған, ақықат), (8-сынып) 336
Кодирование и декодирование информации Кодирование и декодирование информации 149
Создание моделей в среде графического редактора PAINT и в текстовом процессоре WORD Создание моделей в среде графического редактора PAINT и в текстовом процессоре WORD 129
Разработка и визуализация трехмерных моделей кабины лифта Разработка и визуализация трехмерных моделей кабины лифта 134
Алгоритм работы с величинами Алгоритм работы с величинами 143
Двоичное кодирование графической и звуковой информации Двоичное кодирование графической и звуковой информации 131
Особенности реализации пропедевтического курса Особенности реализации пропедевтического курса 93
СИСТЕМЫ СЧИСЛЕНИЯ (9 КЛАСС) СИСТЕМЫ СЧИСЛЕНИЯ (9 КЛАСС) 126
Главное меню. Запуск программ Главное меню. Запуск программ 133
Заветы студента Заветы студента 140
Компьютерные науки Компьютерные науки 344
Будущее в наших руках Будущее в наших руках 168
Презентация по Информатике на тему Табличный процессор Презентация по Информатике на тему Табличный процессор 144
Алгоритм построения диаграммы Алгоритм построения диаграммы 147
Права и обязанности человека в информационном обществе. (Лекция 6) Права и обязанности человека в информационном обществе. (Лекция 6) 157
Двоичное кодирование текстовой информации Двоичное кодирование текстовой информации 129
Статистичне спостереження Статистичне спостереження 90
Системы управления базами данных (СУБД) Системы управления базами данных (СУБД) 120
Презентация к уроку по теме 'Компьютерная графика: области применения, технические средства. Кодирование графической информации' (8 класс) Презентация к уроку по теме 'Компьютерная графика: области применения, технические средства. Кодирование графической информации' (8 класс) 150
Структуры данных. Диаграмма потоков данных Структуры данных. Диаграмма потоков данных 155
ФАЙЛЫ И ПАПКИ ФАЙЛЫ И ПАПКИ 138
Информационное общество Информационное общество 180
Создание искусственного интеллекта Создание искусственного интеллекта 142
Анализ корреляции экспериментальных и расчетных результатов с программами MSC Анализ корреляции экспериментальных и расчетных результатов с программами MSC 122
Презентация по информатике на тему Алгоритмы и программирование Презентация по информатике на тему Алгоритмы и программирование 136
Графический интерфейс Windows Графический интерфейс Windows 110
Тестирование программного обеспечения. (Урок 1) Тестирование программного обеспечения. (Урок 1) 141
Защита от несанкционированного доступа к информации Защита от несанкционированного доступа к информации 126