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

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

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

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

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

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

6 6/ 23 ЗЛП может: ЗЛП может: не иметь ни одного оптимального решения не иметь ни одного оптимального решения допустимой области не существует – система ограничений не совместнадопустимой области не существует – система ограничений не совместна z = max(x 1 +x 2 |x 1 +5x 2 1, x 1 +x 2 5, x 1 0, x 2 0) допустимая область существует, но не ограничивает целевую функциюдопустимая область существует, но не ограничивает целевую функцию z = max(2x 1 +x 2 |0.1x x 2 5, x 1 0, x 2 0) иметь одно оптимальное решение иметь одно оптимальное решение z = max(x 1 +x 2 |0.1x x 2 5, x 1 0, x 2 0) x 1 =50, x 2 =0; z = 50 иметь бесконечно много оптимальных решений иметь бесконечно много оптимальных решений z = max(x 1 +x 2 |0.1x 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 Компактная запись

7 7/ 23 z = max(x 1 +x 2 |0.1x x 2 5, x 1 0, x 2 0) x 1 =50, x 2 =0; z = 50

8 8/ 23 z = max(x 1 +x 2 |0.1x 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

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

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

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

12 12/ 23 z = max(x 1 +x 2 |0.1x x 2 5, x 1 –2x 2 75, x 1 0, x 2 0) x 1 =50, x 2 =0; z = 50 Каноническая форма: max x 1 +x 2 0.1x x 2 +x 3 = 5 x 1 –2x 2 +x 4 = 75 x 1 0, x 2 0, x 3 0, x 4 0 j =1 j = 2 j = 3 i =1 j = 4 i =2 b c j, c i c j, c i i = i =

13 13/ 23 В таблице выделены жирным шрифтом Разрешающий столбец: Разрешающий столбец: столбец с наибольшим положительным c j столбец с наибольшим положительным c j если положительного c j нет, достигнут оптимумесли положительного c j нет, достигнут оптимум Разрешающая строка: Разрешающая строка: для всех положительных a ij в выбранном столбце считаем b i /a ij для всех положительных a ij в выбранном столбце считаем b i /a ij если положительных нет, ц.ф. не ограниченаесли положительных нет, ц.ф. не ограничена выбираем строку, где это значение минимально выбираем строку, где это значение минимально j =1 j = 2 j = 3 i =1 j = 4 i =2 b c j, c i c j, c i i = i =

14 14/ 23 Выполняем обыкновенные жордановы исключения во всей таблице: Выполняем обыкновенные жордановы исключения во всей таблице: для строк i i' : a ijнов = a ij – a i'j a ij' /a i'j', где для строк 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' для строки i =i' : a ijнов = a ij /a i'j' j =1 i =1 (50) j = 2 (0) j = 3 (0) j = 4 i =2 (25) b c j, c i c j, c i i = i = Положительных c j больше нет – достигнут оптимум (в больших задачах для этого требуются тысячи итераций)

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

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

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

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