Презентация на тему: Задачи линейного программирования и их решение в современных вычислительных

Задачи линейного программирования и их решение в современных вычислительных средах
Математическое программирование
Линейное программирование
Формулирование задачи линейного программирования состоит из следующих этапов:
Целевая функция задачи ЛП
Задачи линейного программирования и их решение в современных вычислительных
Задачи линейного программирования и их решение в современных вычислительных
Задачи линейного программирования и их решение в современных вычислительных
Задачи линейного программирования и их решение в современных вычислительных
Общая (смешанная) форма задачи ЛП
Решение (план, программа) задачи ЛП
Методы решения задачи ЛП
Задачи линейного программирования и их решение в современных вычислительных
Пример 1. Задача использования сырья
Пример 1. Задача использования сырья
Задачи линейного программирования и их решение в современных вычислительных
Пример 2. Транспортная задача
Пример 2. Транспортная задача
Пример 2. Транспортная задача
Основные теоремы линейного программирования
Основные теоремы линейного программирования
Графический метод решения задачи ЛП. Применяется только для случаях двух переменных: х 1 и х 2
Графический метод решения задачи ЛП. Общий подход
Примеры решения задач ЛП графическим методом
Пример 1
Задачи линейного программирования и их решение в современных вычислительных
Пример 2
Решение графическим методом
Симплекс-метод решения задачи ЛП
Задачи линейного программирования и их решение в современных вычислительных
1/30
Средняя оценка: 4.5/5 (всего оценок: 22)
Код скопирован в буфер обмена
Скачать (220 Кб)
1

Первый слайд презентации: Задачи линейного программирования и их решение в современных вычислительных средах

Лекция №12

Изображение слайда
2

Слайд 2: Математическое программирование

Математическое программировани е занимается изучением проблем принятия решений, которые могут быть математически сформулированы как задачи нахождения максимума (минимума) функции многих переменных, при заданной системе ограничений на основные переменные задачи. Функция, для которой определяется точка максимума или минимума (оптимума), называется целевой функцией. Часто она обозначается буквами F или С. С ( x 1, x 2, …, x n )  max (min) G 1 ( x 1, x 2, …, x n )≥0 …. G m ( x 1, x 2, …, x n )≥0 Функции С и G могут быть как линейными, так и нелинейными. Ограничения могут быть нестрогими неравенствами ( ≥ или/и ≤) или равенствами. Кроме того, могут быть специфические ограничения. Например, целочисленность одной или нескольких переменных х.

Изображение слайда
3

Слайд 3: Линейное программирование

Линейное программирование (ЛП) – раздел математического программирования, изучающий методы решения задач математического программирования в случае линейной целевой функции и линейных ограничений. Основные математические предположения ЛП: Линейность целевой функции (ЦФ) и ограничений. Определенность (детерминированность) – предполагается, что все параметры модели известны точно или могут быть оценены. Делимость – предполагается, что все основные переменные задачи могут принимать произвольные вещественные значения в определенном диапазоне (бесконечно делимы ). Основателем линейного программирования является советский математик Леонид Витальевич Канторович (1939г.).

Изображение слайда
4

Слайд 4: Формулирование задачи линейного программирования состоит из следующих этапов:

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

Изображение слайда
5

Слайд 5: Целевая функция задачи ЛП

: . C= С ( x 1, x 2, …, x n )= c 1 x 1 + c 2 x 2 +….+ c n x n Или: n – число переменных модели.

Изображение слайда
6

Слайд 6

Формы задачи ЛП Каноническая. Стандартная (нормальная). Общая. (3) (2)

Изображение слайда
7

Слайд 7

Каноническая форма задачи ЛП ЦФ => максимум. Ограничения канонической модели –линейные равенства + условие положительности всех переменных: Или в сокращенной записи: i =1, 2, …, m, J =1, 2, …, n.

Изображение слайда
8

Слайд 8

Стандартная (нормальная) форма задачи ЛП 1. ЦФ = > максимум. Ограничения–линейные неравенства (≤) + условие положительности всех переменных: Или в сокращенной записи: i =1, 2, …, m, J =1, 2, …, n.

Изображение слайда
9

Слайд 9

Стандартная (нормальная) форма ЛП 2. ЦФ = > минимум. Ограничения–линейные неравенства (≥) + условие положительности всех переменных: Или в сокращенной записи: i =1, 2, …, m, J =1, 2, …, n.

Изображение слайда
10

Слайд 10: Общая (смешанная) форма задачи ЛП

Требуется найти максимум или минимум ЦФ. Ограничения неравенства с разными соотношениями (≥, ≤) и равенства. Условие положительности может отсутствовать или иметь место для некоторых переменных. Если все или некоторые ограничения в системе заданы неравенствами, то задачу можно свести к канонической путём преобразования неравенств в уравнения с помощью введения дополнительных переменных. Неравенство со знаком ≥ можно преобразовать в неравенство со знаком ≤ умножением обеих его частей на (-1).

Изображение слайда
11

Слайд 11: Решение (план, программа) задачи ЛП

Множество всевозможных числовых значений x 1, x 2, …, x n, удовлетворяющих системе ограничений, называется  решением  этой системы. Решение системы также часто называется  планом, и немного реже –  программой, но именно отсюда и пошло название « линейное (или математическое) программирование ». Оптимальным решением  задачи линейного программирования называется решение системы, при которых функция цели в   оптимум. Решение задачи линейного программирования называется  вырожденным, если в нём некоторые переменные равны нулю. В противном случае решение является  невырожденным.

Изображение слайда
12

Слайд 12: Методы решения задачи ЛП

Графический метод – для случае двух переменных х 1 и х 2 ( n =2) Симплекс-метод

Изображение слайда
13

Слайд 13

Примеры формулировки задачи линейного программирования

Изображение слайда
14

Слайд 14: Пример 1. Задача использования сырья

Для изготовления двух видов продукции  П 1  и  П 2  требуется четыре вида ресурсов (сырья):  S 1,  S 2,  S 3,  S 4. Запасы сырья – соответственно,   b 1,   b 2,  b 3,  b 4  единицы. На производство единицы продукции П j требуется a i, j единиц сы р ья S i, j =1, 2; i =1, …, 4. Доход от реализации одной единицы продукции П 1 равен   c 1 у.е., а доход от реализации одной единицы продукции  П 2  равен  c 2 у. е. Требуется узнать, сколько единиц  П 1   и сколько единиц  П 2 нужно изготовить из имеющегося запаса сырья, чтобы получить максимальный доход. П 2

Изображение слайда
15

Слайд 15: Пример 1. Задача использования сырья

Для удобства анализа данные представим в виде таблицы: Виды сырья Запасы сырья Виды продукции П 1 П 2 S 1 b 1 a 1,1 a 1,2 S 2 b 2 a 2,1 a 2,2 S 3 b 3 a 3,1 a 3,2 S 4 b 4 a 4,1 a 4,2 Доход от реализации единицы продукции с 1 с 2 П 2

Изображение слайда
16

Слайд 16

Пример 1. Задача использования сырья Обозначим: х 1 –количество изготовляемых единиц продукции П 1, х 2 –количество изготовляемых единиц продукции П 2. Тогда ЦФ равна: C= С ( x 1, x 2 )= c 1 x 1 + c 2 x 2. Ограничения на расход сырья запишутся в виде: В левой части i - го ограничения записан общий расход сырья S i на производство продукции двух видов, а в правой части – запас сырья S i. Кроме того, количество продукции не может быть отрицательным: x 1 ≥0, x 2 ≥0.

Изображение слайда
17

Слайд 17: Пример 2. Транспортная задача

На двух станциях отправления  A 1 и A 2 имеется, соответственно, a 1  и  a 2  единиц некоторого груза. Этот груз следует доставить в три пункта назначения  B 1,  B 2,  B 3,  и в каждый из них должно быть завезено, соответственно, b 1,   b 2, b 3 единиц этого груза. Стоимость перевозки одной единицы груза из пункта  A i  в пункт  B k  равна  c i,k. Составить такой план перевозок, чтобы суммарная стоимость перевозок была минимальной. Считать, что количество всего груза на двух пунктах отправления равно потребности в грузе на всех трех пунктах назначения, то есть: a 1   +   a 2 = b 1 +   b 2 + b 3.

Изображение слайда
18

Слайд 18: Пример 2. Транспортная задача

Расположим исходные данные этой задачи в виде таблицы: Пункт отправления Пункт назначения Запас груза B 1 B 2 B 3 A 1 с 1, 1 с 1,2 с 1,3 a 1 A 2 с 2,1 с 2,2 с 2,3 a 2 Потребность в грузе b 1 b 2 b 3

Изображение слайда
19

Слайд 19: Пример 2. Транспортная задача

Обозначим: x i, k – количество перевезенного груза из пункта A i в пункт B k. Тогда ЦФ (которую нужно минимизировать) равна: Ограничения:

Изображение слайда
20

Слайд 20: Основные теоремы линейного программирования

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

Изображение слайда
21

Слайд 21: Основные теоремы линейного программирования

Теорема 2.   Если существует, и притом единственное, оптимальное решение задачи линейного программирования, то оно совпадает с одной из угловых точек множества допустимых решений. Эта теорема позволяет сделать вывод, что поиски оптимального решения можно ограничить перебором конечного числа угловых точек.

Изображение слайда
22

Слайд 22: Графический метод решения задачи ЛП. Применяется только для случаях двух переменных: х 1 и х 2

Пусть ограничения имеют вид: Кроме того, переменные x 1 и х 2 – неотрицательные. Надо найти значения x 1 и х 2, на которых ЦФ С = с 1 х 1 + с 2 х 2 принимает оптимальное значение.

Изображение слайда
23

Слайд 23: Графический метод решения задачи ЛП. Общий подход

Множество точек на плоскости, удовлетв о ряющих ограничениям –многоугольник. Например, пятиугольник АВС DE. Черная линия, проходящая через начало координат – это линия уровня ЦФ С=0. Перпендикулярный вектор (градиент) к линии уровня показывает направление увеличения ЦФ. Линии уровня (параллельные черной) mn и MN являются ОПОРНЫМИ (имеют одну общую точку с многоугольником решений). Точка А является точкой минимума ЦФ, точка С – точкой максимума ЦФ.

Изображение слайда
24

Слайд 24: Примеры решения задач ЛП графическим методом

Изображение слайда
25

Слайд 25: Пример 1

Пусть ограничения имеют вид: Надо найти значения x 1 и х 2, на которых ЦФ С = х 1 + 3 х 2 принимает макс имальное значение.

Изображение слайда
26

Слайд 26

Решение графическим методом Желтым цветом изображены линии, полученные из ограничений. Множество допустимых значений – четырех угольник АВС D. Черная линия, проходящая через начало координат – это линия уровня ЦФ С=0. Перпендикулярный вектор к линии уровня ( градиент) показывает направление увеличения ЦФ. Перемещая линию уровня в направлении градиента, найдем опорные прямые. Точка А является точкой минимума ЦФ, точка В – точкой максимума ЦФ. Подставляя в ЦФ координаты точки В x 1 =2, x 2 =4, найдем максимальное значение ЦФ: Cmax =14.

Изображение слайда
27

Слайд 27: Пример 2

Пусть ограничения имеют вид: Надо найти значения x 1 и х 2, на которых ЦФ С = 5 х 1 + 6 х 2 принимает м инимальное значение.

Изображение слайда
28

Слайд 28: Решение графическим методом

Множество допустимых значений – открытая область N 1 ВС N 2. Черная линия, проходящая через начало координат – это линия уровня ЦФ С=0. Перпендикулярный вектор к линии уровня (градиент) показывает направление увеличения ЦФ. Ближайшее от начала координат опорной положение линии уровня – в точке B. Эта точка является точкой минимума ЦФ точкой максимума ЦФ. Подставляя в ЦФ координаты точки В x 1 =2, x 2 = 2, найдем минимальное значение ЦФ: Cmax = 22.

Изображение слайда
29

Слайд 29: Симплекс-метод решения задачи ЛП

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

Изображение слайда
30

Последний слайд презентации: Задачи линейного программирования и их решение в современных вычислительных

Excel: Поиск решения Mathcad: блок Given и функции нахождения оптимума Инструменты решения задач ЛП Matlab : функция linprog

Изображение слайда