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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Применение линейного программирования в математических моделях. Доклад-сообщение содержит 59 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

Известные ученые-экономисты

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

3.2. Задача линейного программирования Это стандартная форма записи

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Линейное программирование Приведенный план местности изображает возвышенность с наивысшей отметкой 84,4 м. Местность полого понижается вправо и более круто влево. Правая пониженная часть местности имеет отметку 81 м, что видно из записи, сделанной около крайней правой горизонтали. На рис. 2, б для наглядности нарисован участок местности. Проекции с числовыми отметками применяются в геодезии и топографическом черчении.

Слайд 12

Описание слайда:

Линейное программирование Найти самую высокую точку области X принадлежит D. Высота – функция координат!

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

3.2. z = max(x1+x2|0.1x1+0.2x2  5, x1  0, x2  0) x1=50, x2 =0; z = 50

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

3.2. z = max(x1+x2|x1+5x2  1, x1+x2  5, x1  0, x2  0)

Слайд 17

Описание слайда:

3.2. z = max(2x1+x2|0.1x1+0.1x2  5, x1  0, x2  0)

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

Задача о диете

Слайд 20

Описание слайда:

Задача о диете

Слайд 21

Описание слайда:

Задача о диете

Слайд 22

Описание слайда:

Задача о диете=Задача о смеси

Слайд 23

Описание слайда:

3.3. Симплексный метод Ограничения ЗЛП в канонической форме приводятся к виду

Слайд 24

Описание слайда:

3.3. Симплексный метод Подставляя в ЦФ вместо базисных переменных их выражения через свободные переменные из системы

Слайд 25

Описание слайда:

3.3. Симплексный метод Геометрическая интерпретация. Аналитическому переходу от одного базиса к другому соответствует переход от одной вершины многогранника (множества допустимых решений) к другой, в которой целевая функция имеет не меньшее значение. Этот факт основан на том, что вершинам многоугольника множества допустимых решений соответствуют базисные решения системы ограничений.

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

3.3. z = max(x1+x2|0.1x1+0.2x2  5, x1–2x2  20, x1  0, x2  0)

Слайд 28

Описание слайда:

Слайд 29

Описание слайда:

3.3. z = max(x1+x2|0.1x1+0.2x2  5, x1–2x2  20, x1  0, x2  0) Каноническая форма: max x1+x2 0.1x1+0.2x2+x3 = 5 x1–2x2 +x4 = 20 x1  0, x2  0, x3  0, x4  0

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

Слайд 34

Описание слайда:

Слайд 35

Описание слайда:

3.3. z = max(x1+x2|0.1x1+0.2x2  5, x1–2x2  20, x1  0, x2  0)

Слайд 36

Описание слайда:

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

3.3. Симплексный метод Определение: Говорят, что ограничение задачи ЛП, имеет предпочтительный вид, если при неотрицательной правой части (bi) левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.

Слайд 39

Описание слайда:

3.3. 1. случай: система ограничений имеет вид

Слайд 40

Описание слайда:

3.3. 2. случай: система ограничений имеет вид (напр. Задача о диете)

Слайд 41

Описание слайда:

3.3. метод искусственного базиса вводится искусственный базис: 1. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные (вводится искусственный базис:)