Игры по математике
<<  Математические модели и оптимальные процессы в макросистемах "Своя игра" по математике  >>
Лекция 3. Применение линейного программирования в математических
Лекция 3. Применение линейного программирования в математических
Литература
Литература
3.1. Принцип оптимальности в планировании и управлении
3.1. Принцип оптимальности в планировании и управлении
3.2. Задача линейного программирования
3.2. Задача линейного программирования
3.2. Задача линейного программирования
3.2. Задача линейного программирования
3.2. Задача линейного программирования
3.2. Задача линейного программирования
3.2. Задача линейного программирования
3.2. Задача линейного программирования
3.2
3.2
3.2
3.2
3.2
3.2
3.2
3.2
3.2
3.2
3.2
3.2
3.3. Симплексный метод
3.3. Симплексный метод
3.3
3.3
3.3
3.3
3.3
3.3
3.3
3.3
3.3
3.3
3.4. Экономические приложения линейного программирования
3.4. Экономические приложения линейного программирования
3.4. Экономические приложения линейного программирования
3.4. Экономические приложения линейного программирования
3.5. Программное обеспечение линейного программирования
3.5. Программное обеспечение линейного программирования
3.5
3.5

Презентация на тему: «Применение линейного программирования в математических моделях». Автор: Н. Светлов. Файл: «Применение линейного программирования в математических моделях.ppt». Размер zip-архива: 390 КБ.

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

содержание презентации «Применение линейного программирования в математических моделях.ppt»
СлайдТекст
1 Лекция 3. Применение линейного программирования в математических

Лекция 3. Применение линейного программирования в математических

моделях

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

1/23

2 Литература

Литература

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

2/23

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

3 3.1. Принцип оптимальности в планировании и управлении

3.1. Принцип оптимальности в планировании и управлении

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

3/23

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

4 3.2. Задача линейного программирования

3.2. Задача линейного программирования

Линейная целевая функция

Линейные ограни-чения

Это развёрнутая форма записи

Условия неотрицательности переменных

4/23

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

5 3.2. Задача линейного программирования

3.2. Задача линейного программирования

Линейная целевая функция

Линейные ограни-чения

Это каноническая форма записи

Условия неотрицательности переменных

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

5/23

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

6 3.2. Задача линейного программирования

3.2. Задача линейного программирования

Линейная целевая функция

Линейные ограни-чения

Это матричная форма записи Она тождественна канонической форме

Условия неотрицательности переменных

6/23

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

7 3.2. Задача линейного программирования

3.2. Задача линейного программирования

Линейная целевая функция

Линейные ограни-чения

Это стандартная форма записи

Условия неотрицательности переменных

7/23

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

8 3.2

3.2

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

8/23

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

9 3.2

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

9/23

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

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

10 3.2

3.2

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

10/23

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

11 3.2

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

11/23

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

12 3.2

3.2

z = max(x1+x2|x1+5x2 ? 1, x1+x2 ? 5, x1 ? 0, x2 ? 0)

Несовместность системы ограничений

12/23

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

13 3.2

3.2

z = max(2x1+x2|0.1x1+0.1x2 ? 5, x1 ? 0, x2 ? 0)

Неограниченность целевой функции

13/23

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

14 3.3. Симплексный метод

3.3. Симплексный метод

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

14/23

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

15 3.3

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

j =1

j = 2

j = 3 i =1

j = 4 i =2

b

cj , ci ?

1

1

0

0

0

i = 1

0.1

0.2

1

0

5

i = 2

1

-2

0

1

75

15/23

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

16 3.3

3.3

j =1

j = 2

j = 3 i =1

j = 4 i =2

b

cj , ci ?

1

1

0

0

0

i = 1

0.1

0.2

1

0

5

i = 2

1

-2

0

1

75

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

В таблице выделены жирным шрифтом

16/23

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

17 3.3

3.3

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

j =1 i =1 (50)

j = 2 (0)

j = 3 (0)

j = 4 i =2 (25)

b

cj , ci ?

0

-1

-10

0

-50

i = 1

1

2

10

0

50

i = 2

0

-4

-10

1

25

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

17/23

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

18 3.3

3.3

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

18/23

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

19 3.3

3.3

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

19/23

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

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

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

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

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

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

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

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

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

20/23

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

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

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

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

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

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

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

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

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

21/23

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

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

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

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

Найти XA

22/23

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

23 3.5

3.5

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

Найти XA

23/23

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

«Применение линейного программирования в математических моделях»
http://900igr.net/prezentacija/matematika/primenenie-linejnogo-programmirovanija-v-matematicheskikh-modeljakh-152721.html
cсылка на страницу
Урок

Математика

71 тема
Слайды
900igr.net > Презентации по математике > Игры по математике > Применение линейного программирования в математических моделях