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

Лекция 3. Применение линейного программирования в математических моделях Литература Известные ученые-экономисты 3.1. Принцип оптимальности в планировании и управлении Задачи линейного программирования 3.2. Задача линейного программирования 3.2. Задача линейного программирования Лекция 3. Применение линейного программирования в математических моделях Правила приведения ЗЛП к каноническому виду: Лекция 3. Применение линейного программирования в математических моделях 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.4. Экономические приложения линейного программирования 3.4. Экономические приложения линейного программирования 3.5. Программное обеспечение линейного программирования 3.5.
1/40
Средняя оценка: 4.0/5 (всего оценок: 12)
Скачать (456 Кб)
Код скопирован в буфер обмена
1

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

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

2

Слайд 2: Литература

2 / 23 Литература Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. — глава 2. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, 2001. Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: Изд-во АН СССР, 1960. Линейное программирование. Оптимальное распределение ресурсов. Методические указания для выполнения лабораторных работ для студентов направлений подготовки бакалавриата 120700, 080100 и 080200./НМСУ «Горный». Сост. В.В. Беляев, Т.Р. Косовцева. СПб, 2012., 62 с.

3

Слайд 3: Известные ученые-экономисты

Леонид Витальевич Канторович родился 19 января 1912г. в Санкт-Петербурге в семье врача. В 18 лет он закончил математико-механический факультет Ленинградского университета (1930) и уже через четыре года получил звание профессора. Л.В.Канторович является одним из основателей отечественных школ функционального анализа. вычислительной математики, языков программирования. С 1938г. интересы Л.В.Канторовича были неразрывно связаны с экономическими исследованиями и решением народнохозяйственных проблем. Крупнейшим его открытием является введение в математическую и экономическую науки понятия "линейное программирование" (1939). Линейное программирование является универсальной математической моделью оптимального функционирования экономических систем. Основная заслуга Л.В.Канторовича заключается в разработке единого подхода к широкому кругу экономических задач о наилучшем использовании ресурсов на базе линейного программирования.

4

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

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

5

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

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

6

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

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

7

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

7 / 23 3.2. Задача линейного программирования Это каноническая форма записи Линейная целевая функция (ЦФ) Линейные ограни-чения ( фазовые ограничения) Условия неотрицательности переменных (естественные ограничения) Любую ЗЛП можно записать в каноническом виде (ограничения – равенства, свободные члены неотрицательны, решается на максимум)

8

Слайд 8

Пространство допустимых значений всегда имеет форму выпуклого множества. Множество называется выпуклым, если отрезок прямой, соединяющий любые две точки этого множества, полностью принадлежит этому множеству. 8 / 23

9

Слайд 9: Правила приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, причем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-» a 11 x 1 +a 12 x 2 +...+a 1n x n <=b 1 Вводим переменную x n+1 =b 1 -a 11 x 1 -a 12 x 2 +...+a 1n x n. Тогда неравенство запишется в виде: a 11 x 1 +a 12 x 2 +...+a 1n x n +x n+1 =b 1 В каждое из неравенств вводится своя " уравнивающая ” переменная, после чего система ограничений становится системой уравнений. 9 / 23

10

Слайд 10

2. Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных X k =X k -X l где: X k >=0, X l >=0 l - свободный индекс 3. Если в ограничениях правая часть отрицательна, то следует умножить это ограничение на (-1) 4. Если исходная задача была задачей на минимум, то введением новой целевой функции F 1 = -F мы преобразуем нашу задачу на минимум функции  F в задачу на максимум функции  F 1. Таким образом, всякую задачу линейного программирования можно сформулировать в канонической форме. 10 / 23

11

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

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

12

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

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

13

Слайд 13: 3.2

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

14

Слайд 14: 3.2

14 / 23 3.2. ЗЛП может: не иметь ни одного оптимального решения допустимой области не существует – система ограничений не совместна z = max( x 1 + x 2 | x 1 +5 x 2  1, x 1 + x 2  5, x 1  0, x 2  0) допустимая область существует, но не ограничивает целевую функцию z = max( 2 x 1 + x 2 |0.1 x 1 +0.1 x 2  5, x 1  0, x 2  0) иметь одно оптимальное решение z = max( x 1 + x 2 |0.1 x 1 +0. 2 x 2  5, x 1  0, x 2  0) x 1 =50, x 2 =0; z = 50 иметь бесконечно много оптимальных решений z = max( x 1 + x 2 |0.1 x 1 +0. 1 x 2  5, x 1  0, x 2  0) x 1 =50, x 2 =0; z = 50 … x 1 =0, x 2 =50; z = 50 Компактная запись

15

Слайд 15: 3.2

15 / 23 3.2. z = max( x 1 + x 2 |0.1 x 1 +0. 2 x 2  5, x 1  0, x 2  0) x 1 =50, x 2 =0; z = 50

16

Слайд 16: 3.2

16 / 23 3.2. z = max( x 1 + x 2 |0.1 x 1 +0. 1 x 2  5, x 1  0, x 2  0) x 1 =50, x 2 =0; z = 50 … x 1 =0, x 2 =50; z = 50

17

Слайд 17: 3.2

17 / 23 3.2. z = max( x 1 + x 2 | x 1 +5 x 2  1, x 1 + x 2  5, x 1  0, x 2  0) Несовместность системы ограничений

18

Слайд 18: 3.2

18 / 23 3.2. z = max( 2 x 1 + x 2 |0.1 x 1 +0.1 x 2  5, x 1  0, x 2  0) Неограниченность целевой функции

19

Слайд 19: Геометрический смысл задачи линейного программирования

20

Слайд 20: Задача о диете

Количество Корма 1 Вид 2 вид Цена 5 2 Кол-во x1 x2 =5*x1+2*x2 <- стоимость Содержание Факт. Норма А 5 3 =5*x1+3*x2 >= 225 B 2.5 3 =2.5*x1+3*x3 >= 150 C 1 1.3 =1*x1+1*x4 >= 80 Составить задачу ЛП, позволяющую оптимизировать расход кормов, и привести ее к каноническому виду. Для откорма животных употребляют два вида кормов; стоимость 1 кг корма I вида - 5  у.е., а корма - II вида 2 у.е. В каждом килограмме корма I вида содержится 5 ед. питательного вещества   А, 2.5 ед. питательного вещества B и 1 ед. питательного вещества C. В каждом килограмме корма II вида содержится соответственно 3, 3 и 1.3 ед. Суточный рацион предусматривает питательных единиц  A не менее 225 ед., типа B - не менее 150 ед. и типа C - не менее 80 ед. Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты были минимальны?

21

Слайд 21: Задача о диете

Количество Корма 1 Вид 2 вид Цена 5 2 Кол-во x1 x2 =5*x1+2*x2 <- стоимость Содержание Факт. Норма А 5 3 =5*x1+3*x2 >= 225 B 2.5 3 =2.5*x1+3*x3 >= 150 C 1 1.3 =1*x1+1*x4 >= 80 Задача ЛП Задача ЛП в канонической форме !

22

Слайд 22: Задача о диете

В 1982 г. Джорджу Стиглеру была присуждена Нобелевская премия за труды по теории экономического регулирования (совсем не проблемы линейного программирования!) Еще в 1945 г. без помощи линейного программирования ДЖОРДЖ СТИГЛЕР. составил "самый дешевый набор продуктов", явившийся фактически прообразом потребительской корзины. Пытался найти наиболее дешевый рацион, удовлетворяющий 9 диетическим требования, сформулированным в 1943 году. В наборе продуктов было 77 наименований, от пшеничной муки до клубничного джема. Подводя итоги своей работы в 1945 «Затраты на питание» : «По всей видимости не существует универсального метода нахождения минимума линейной функции при «соблюдении линейных ограничений. Разработав в конце 40-х годов симплекс-метод, Георг Данциг совершил переворот. 70 лет назад решение задачи составления рациона вызывало затруднения у лучших экономистов мира, теперь доступно для начинающих студентов.

23

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

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

24

Слайд 24: Алгоритм симплексного метода решения задач линейного программирования

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее: Привести задачу к каноническому виду Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений) Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода Если выполняется признак единственности оптимального решения, то решение задачи заканчивается Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения 24 / 23

25

Слайд 25: 3.3

25 / 23 3.3. z = max( x 1 + x 2 |0.1 x 1 +0. 2 x 2  5, x 1 –2 x 2  7 5, x 1  0, x 2  0) x 1 =50, x 2 =0; z = 50 Каноническая форма: max x 1 + x 2 0.1 x 1 +0. 2 x 2 + x 3 = 5 x 1 –2 x 2 + x 4 = 7 5 x 1  0, x 2  0, x 3  0, x 4  0 Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

26

Слайд 26: 3.3

26 / 23 В таблице выделены жирным шрифтом 3.3. Разрешающий столбец: столбец с наибольшим по модулю отрица тельн о м c j если отрицате льного c j нет, достигнут оптимум Разрешающая строка: для всех положительных a ij в выбранном столбце считаем b i / a ij если положительных нет, ц.ф. не ограничена выбираем строку, где это значение минимально x1 x2 x3 x4 b вспомогат. x3 0.1 0.2 1 0 5 50 x4 1 -2 0 1 75 75 F -1 -1 0 0 0

27

Слайд 27: 3.3

27 / 23 3.3. Выполняем обыкновенные жордановы исключения во всей таблице: для строк i  i' : a ij нов = a ij – a i'j a ij' / a i'j', где i' и j' – координаты выбранных (разрешающих) строки и столбца для строки i = i' : a ij нов = a ij / a i'j' Отрицат ельных c j больше нет – достигнут оптимум (в больших задачах для этого требуются тысячи итераций) x1 x2 x3 x4 b x1 1 2 10 0 50 x4 0 -4 -10 1 25 F 0 1 10 0 50

28

Слайд 28

28 / 23

29

Слайд 29

29 / 23

30

Слайд 30

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

31

Слайд 31: Симплексный метод

32

Слайд 32: 3.3

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

33

Слайд 33: 3.3

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

34

Слайд 34: Двойственная задача

Правила: Каждому i -му ограничению исходной задачи соответствует переменная двойственной задачи u i (двойственная переменная). Каждой j -ой переменной исходной задачи соответствует ограничение двойственной задачи. Матрица коэффициентов ограничений двойственной задачи является транспонированной Коэффициенты при двойственных переменных в целевой функции двойственной задачи равны правым частям ограничений исходной задачи. Если исходная задача была на нахождение максимума, то двойственная будет на нахождение минимума двойственные переменные принято называть двойственными оценками U i

35

Слайд 35: Свойства решений

Значения целевых функций для оптимальных решений прямой и двойственной задач совпадают Двойственная оценка называется теневой ценой теневая цена u i является коэффициентом при b i => показывает, как изменится целевая функция при изменении i- го ресурса на единицу. Теневая цена показывает предельную величину цены на данный ресурс, которую целесообразно платить за него, чтобы производство продукции давало прибыль.

36

Слайд 36: ЗАДАЧА ОБ ОПТИМАЛЬНОМ РАСПРЕДЕЛЕНИИ РЕСУРСОВ

Здесь (2.1) - целевая функция (ЦФ); (2.2) - система ограничений; (2.3) - естественные граничные условия;

37

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

37 / 23 3.4. Экономические приложения линейного программирования Матрица потребности в ресурсах для обеспечения единичного объёма производства в каждой отрасли. Строки – ресурсы, столбцы – отрасли. Объёмы невоспроизводимых ресурсов (земельные угодья, трудовые ресурсы, запасы полезных ископаемых и т.п.), имеющиеся в распоряжении народного хозяйства Матрица затрат (+) и выпуска (-) ресурсов при единичном объёме производства в каждой отрасли. Строки – ресурсы, столбцы – отрасли. Вектор, состоящий из нулей Матрица выпуска (+) конечной продукции при единичном объёме производства в каждой отрасли. Строки – виды продукции, столбцы – отрасли. Вектор объёмов потребления каждого вида конечной продукции при единичном (стандартном) уровне удовлетворения потребностей Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

38

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

38 / 23 3.4. Экономические приложения линейного программирования Вектор цен продукции (за вычетом НДС), руб./ед. Вектор цен ресурсов (включая НДС), руб./ед. Матрица затрат ресурсов на производство и реализацию единицы продукции, ед.рес./ед.прод. Вектор наличия (начальных запасов) ресурсов Матрица объёмов обязательств, выполняемых вследствие реализации единицы продукции каждого вида Объёмы обязательств, имеющихся у предприятия и учитываемых при оптимальном планировании (выполнение которых зависит от составленного плана)

39

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

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

40

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

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

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