Линейное программирование - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

Оглавление Линейное программирование Симплекс-метод Основная теорема линейного программирования Графический метод решения Задача на максимум Геометрический метод решения задач линейного программирования Задача с бесконечным множеством оптимальных решений Усложнённые постановки транспортной задачи Многоэтапная задача Двойственные задачи Закрытая транспортная задача Метод потенциалов

Слайд 2

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

Линейное программирование Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования.

Слайд 3

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

Задачи линейного программирования можно решить аналитическим путем и графическим методом. В геометрии есть такое понятие, как "симплекс". С учетом этого понятия аналитический метод решения задач линейного программирования называется симплекс-методом.

Слайд 4

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

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

Слайд 5

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

Задача линейного программирования записывается следующим образом:

Слайд 6

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

Аналитический метод решения задач ЛП: 1. Найти вершины ОДР. 2. Определить значения целевой функции в вершинах. 3. Вершина, в которой ЦФ приобретает оптимальное (максимальное или минимальное) значение, является оптимальной вершиной. 4. Координаты этой вершины и являются искомыми оптимальными значениями переменных.

Слайд 7

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

Основная теорема линейного программирования Целевая функция задачи линейного программирования достигает своего экстремума (минимума или максимума) в вершине допустимой области. Если целевая функция достигает экстремального значения более, чем на одной вершине, то она достигает того же значения в любой точке, являющейся выпуклой комбинацией этих вершин.

Слайд 8

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

В том случае, когда требуется найти минимум функции можно перейти к нахождению максимума функции поскольку

Слайд 9

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

Графический метод решения

Слайд 10

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

Будет изготовлено: x1 единиц изделий вида А x2 единиц изделий вида В Прибыль от их реализации составит: → max

Слайд 11

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

Слайд 12

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

Координаты точки В и определяют план выпуска изделий А и В, при котором прибыль от их реализации является максимальной. Найдем координаты точки В как точки пересечения прямых II и III. Следовательно, ее координаты удовлетворяют уравнениям этих прямых Решив эту систему уравнений, получим: Оптимальный план x* = (12, 18) f(x*)= 1080

Слайд 13

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

Слайд 14

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

Задача на максимум Сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной?

Слайд 15

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

Слайд 16

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

Слайд 17

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

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

Слайд 18

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

Основные понятия Линия уровня – линия, вдоль которой целевая функция принимает одно и то же фиксированное значение (a). F = c1x1 + c2x2 = a

Слайд 19

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

Слайд 20

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

Геометрический смысл

Слайд 21

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

Условие задачи 4x1 + 2x2  MAX 100x1 + 200x2 ≤ 1200 50x1 + 50x2 ≤ 400 x1 + x2 ≥ 4 x1 ≥ 0 x2 ≥ 0

Слайд 22

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

Слайд 23

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

Слайд 24

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

Слайд 25

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

Слайд 26

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

Слайд 27

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

Ответ и проверка

Слайд 28

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

Задача с бесконечным множеством оптимальных решений

Слайд 29

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

Координаты точек оптимальных решений α(2,5 ; 7,5) + (1 - α)(4 ; 0) = =(2,5α ; 7,5α) + (4 - 4α ; 0) = =(4 – 1,5α ; 7,5α) (4 ; 0), (3 ; 5), (2,5 ; 7,5) 0 ≤ α ≤ 1

Слайд 30

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

Задача не имеющая оптимального решения

Слайд 31

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

Задача не имеющая оптимального решения

Слайд 32

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

Усложнённые постановки транспортной задачи

Слайд 33

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

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

Слайд 34

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

Известно, что на участке дороги от поставщика А2 до потребителя В1 пропускная способность ограничена и здесь можно провезти не более 15 единиц данного груза. Известно, что на участке дороги от поставщика А2 до потребителя В1 пропускная способность ограничена и здесь можно провезти не более 15 единиц данного груза. Каких-либо ограничений по другим участкам сети дорог нет.

Слайд 35

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

Дополнительные ограничения, если они существенны, т.е. если их учёт влечёт за собой изменение плана, приводят к ухудшению функционала. Дополнительные ограничения, если они существенны, т.е. если их учёт влечёт за собой изменение плана, приводят к ухудшению функционала. Понятно, что подобное построение матрицы может быть сделано введением дополнительно строки, а не столбца (Таблица 3)

Слайд 36

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

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

Слайд 37

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

Многоэтапная задача

Слайд 38

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

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

Слайд 39

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

Способ Ордена-Маша

Слайд 40

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

Слайд 41

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

Слайд 42

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

Двойственные задачи

Слайд 43

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

Любая задача линейного программирования (даже не имеющая решений) имеет двойственную задачу. Прежде чем строить двойственную задачу в задаче на max все неравенства приводят к знаку , а в задаче на min – к . Т. о. в задаче на max знаки могут быть либо « », либо «=».

Слайд 44

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

Правило построения двойственной задачи: Если исходная задача на max, то двойственная на min и наоборот. В двойственной задаче столько переменных, сколько ограничений в исходной, прием эти переменные соответствуют ограничениям и наоборот. Коэффициентами целевой функции двойственной задачи являются правые части ограничений исходной задачи. Матица коэффициентов ограничений двойственной задачи получается транспонированием матрицы коэффициентов ограничений исходной задачи. Правыми частями ограничений двойственной задачи являются коэффициенты целевой функции исходной. Ограничениям неравенствам исходной задачи соответствуют неотрицательные переменные двойственной задачи, а ограничениям равенствам – переменные любого знака и наоборот.

Слайд 45

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

f(x) g(y) - основное неравенство двойственности f(x) g(y) - основное неравенство двойственности Теорема1: Если исходная задача имеет оптимальный план x*, то двойственная задача также имеет оптимальный план y*, причем значения функций на этих планах равны: f(x*)=g(y*) Теорема2: Если исходная и двойственная задачи имеют планы, то они имеют и оптимальные планы, причем f(x*)=g(y*)

Слайд 46

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

Признаки оптимальности для двойственных задач Признак1: Если исходная и двойственная задачи имеют планы X и Y, причем f(X)=g(Y), то эти планы оптимальные. Определение: Ограничения расположенные на одной строке в схеме пары двойственных задач называют сопряженными. Признак2: Для того, чтобы планы X и Y исходной и двойственной задач были оптимальны, необходимо и достаточно чтобы на этих планах хотя бы одно из каждой пары сопряженных ограничений являлось равенством. Второй признак позволяет зная оптимальный план одной из задач найти оптимальный план другой задачи.

Слайд 47

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

Решим исходную задачу симплекс методом:

Слайд 48

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

Закрытая транспортная задача. Метод потенциалов

Слайд 49

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

Определение Закрытая транспортная задача – задача о перевозке однородной продукции, когда имеется m поставщиков, для которых известны запасы, и n потребителей, для которых известны потребности, а также известны стоимости перевозки одной единицы продукции от каждого поставщика к каждому потребителю, причем суммарные запасы поставщиков равны суммарным потребностям потребителей.

Слайд 50

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

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

Слайд 51

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

Обозначения bi – множество поставщиков aj – множество потребителей сij – цены перевозок единицы товара от i-го поставщика к j-му потребителю xij – планируемый объем перевозок от i-го поставщика к j-му потребителю