2.2.3. Симплекс-метод. Сущность метода Первый шаг. Найти допустимое решение (план), соответствующее одной из вершин области допустимых решений. Второй. - презентация

1 Симплекс-метод

2 Сущность метода Первый шаг. Найти допустимое решение (план), соответствующее одной из вершин области допустимых решений. Второй шаг. Проверить, оптимально ли найденное решение (план). Если оптимально, вычисления окончены. Если нет, переходим к следующему шагу. Третий шаг. Переход к другой вершине (другому допустимому решению), в которой значение целевой функции больше (меньше), проверка его на оптимальность… Первый шаг. Найти допустимое решение (план), соответствующее одной из вершин области допустимых решений. Второй шаг. Проверить, оптимально ли найденное решение (план). Если оптимально, вычисления окончены. Если нет, переходим к следующему шагу. Третий шаг. Переход к другой вершине (другому допустимому решению), в которой значение целевой функции больше (меньше), проверка его на оптимальность…

3 Сущность метода Метод применим к любой задаче линейного программирования в канонической форме: Количество неизвестных (n) в системе ограничений должно быть больше количества уравнений (m). Метод применим к любой задаче линейного программирования в канонической форме: Количество неизвестных (n) в системе ограничений должно быть больше количества уравнений (m).

4 Сущность метода Для начала работы по симплекс-методу необходимо привести систему уравнений к допустимому виду, то есть, выразить какие-то из неизвестных через остальные. Неизвестные, которые выражаются через остальные неизвестные, называются базисными, а весь набор этих неизвестных – допустимым базисом. Остальные неизвестные называются свободными. Количество базисных переменных должно равняться количеству уравнений в системе. Для начала работы по симплекс-методу необходимо привести систему уравнений к допустимому виду, то есть, выразить какие-то из неизвестных через остальные. Неизвестные, которые выражаются через остальные неизвестные, называются базисными, а весь набор этих неизвестных – допустимым базисом. Остальные неизвестные называются свободными. Количество базисных переменных должно равняться количеству уравнений в системе.

5 Сущность метода Для наглядности предположим, что система ограничений уже приведена к допустимому виду:

6 Сущность метода Решения системы ограничений, получаемые в случае, когда свободные переменные равны нулю, называются базисными. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Решения системы ограничений, получаемые в случае, когда свободные переменные равны нулю, называются базисными. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны.

7 Сущность метода Фундаментальная теорема симплекс- метода: среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Таким образом симплекс-метод представляет собой процедуру направленного перебора опорных решений. Фундаментальная теорема симплекс- метода: среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Таким образом симплекс-метод представляет собой процедуру направленного перебора опорных решений.

8 Сущность метода Далее необходимо преобразовать целевую функцию, заменив в ней каждое базисное неизвестное через свободные переменные. Для исключения базисных неизвестных из целевой функции нужно умножить первое уравнение системы ограничений на c 1, второе на c 2, и т.д., сложить полученные произведения и вычесть целевую функцию. Далее необходимо преобразовать целевую функцию, заменив в ней каждое базисное неизвестное через свободные переменные. Для исключения базисных неизвестных из целевой функции нужно умножить первое уравнение системы ограничений на c 1, второе на c 2, и т.д., сложить полученные произведения и вычесть целевую функцию.

9 Сущность метода Получим: или где. Получим: или где.

10 Сущность метода Критерий оптимальности базисного решения ЗЛП: Базисное решение является оптимальным решением задачи линейного программирования тогда и только тогда, когда все j 0. Критерий единственности базисного оптимального решения ЗЛП: Базисное решение является единственным оптимальным решением задачи линейного программирования тогда и только тогда, когда всеj строго положительны. Критерий оптимальности базисного решения ЗЛП: Базисное решение является оптимальным решением задачи линейного программирования тогда и только тогда, когда все j 0. Критерий единственности базисного оптимального решения ЗЛП: Базисное решение является единственным оптимальным решением задачи линейного программирования тогда и только тогда, когда всеj строго положительны.

11 Сущность метода Критерий неразрешимости ЗЛП: Если есть хотя бы одна свободная неизвестная, такая что коэффициент j при ней отрицателен, а в первых m уравнениях системы ограничений среди коэффициентов при ней нет ни одного положительного, то задача линейного программирования неразрешима в силу неограниченности целевой функции на множестве неотрицательных решений системы ограничений. Критерий неразрешимости ЗЛП: Если есть хотя бы одна свободная неизвестная, такая что коэффициент j при ней отрицателен, а в первых m уравнениях системы ограничений среди коэффициентов при ней нет ни одного положительного, то задача линейного программирования неразрешима в силу неограниченности целевой функции на множестве неотрицательных решений системы ограничений.

12 Сущность метода Критерий неразрешимости ЗЛП: Если есть хотя бы одна свободная неизвестная, такая что коэффициент j при ней отрицателен, а в первых m уравнениях системы ограничений среди коэффициентов при ней нет ни одного положительного, то задача линейного программирования неразрешима в силу неограниченности целевой функции на множестве неотрицательных решений системы ограничений. Критерий неразрешимости ЗЛП: Если есть хотя бы одна свободная неизвестная, такая что коэффициент j при ней отрицателен, а в первых m уравнениях системы ограничений среди коэффициентов при ней нет ни одного положительного, то задача линейного программирования неразрешима в силу неограниченности целевой функции на множестве неотрицательных решений системы ограничений.

13 Основные этапы решения задачи 1. Выделение допустимого базиса и преобразование целевой функции. 2. Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности. 3. Проверка полученного решения на оптимальность. Если решение не оптимально, то 4. Поиск другого допустимого базисного решения, при котором целевая функция достигает как минимум не меньшего значения. П. 3 и 4 повторяются до нахождения оптимального решения 1. Выделение допустимого базиса и преобразование целевой функции. 2. Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности. 3. Проверка полученного решения на оптимальность. Если решение не оптимально, то 4. Поиск другого допустимого базисного решения, при котором целевая функция достигает как минимум не меньшего значения. П. 3 и 4 повторяются до нахождения оптимального решения

14 Симплекс-таблица Пусть задача приведена к виду:

15 Симплекс-таблица Базисbibi c1c1 c2c2 …cmcm c m+1 …cncn x1x1 x2x2 …xmxm x m+1 …xnxn c1c1 x1x1 b1b1 10…0a 1m+1 …a 1n c2c2 x2x2 b2b2 01…0a 2m+1 …a 2n ………………………… cmcm xmxm bmbm 00…1a mm+1 …a mn 00…0 m+1 …m

16 Симплекс-таблица: алгоритм решения 1. Просматривается последняя строка таблицы, среди коэффициентов этой строки (исключая столбец свободных членов) выбирается наименьшее отрицательное число. Если такового нет, то исходное базисное решение является оптимальным.

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

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

19 Симплекс-таблица: алгоритм решения 4. Базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Новая таблица строится по следующему алгоритму.

20 Симплекс-таблица: алгоритм решения 4 а) Делим ключевую строку на разрешающий элемент. 4 б) К каждой из остальных строк таблицы прибавляем вновь полученную строку, умноженную на такое число, чтобы в клетке ключевого столбца в этой строке появился 0. То же самое делаем и с индексной строкой. 4 а) Делим ключевую строку на разрешающий элемент. 4 б) К каждой из остальных строк таблицы прибавляем вновь полученную строку, умноженную на такое число, чтобы в клетке ключевого столбца в этой строке появился 0. То же самое делаем и с индексной строкой.

21 Симплекс-таблица: алгоритм решения 5. Новая симплекс-таблица отвечает новому базисному решению. Проверяем новое решение на оптимальность, если решение не оптимально, то повторяем алгоритм.

22 Пример Для производства четырех видов изделий A1, A2, A3, A4 завод должен использовать три вида сырья I, II, III. Требуется составить план выпуска, обеспечивающий максимальную прибыль.. Для производства четырех видов изделий A1, A2, A3, A4 завод должен использовать три вида сырья I, II, III. Требуется составить план выпуска, обеспечивающий максимальную прибыль.. Виды сырья Запасы сырья Технологические коэффициенты A1 A2 A3A4A4 I II III Прибыль 622,54

23 Пример Математическая модель задачи:. Математическая модель задачи:.

24 Пример Приведение задачи к каноническому виду: Примем за базисные переменные x 5, x 6, x 7. Тогда опорное решение: (0; 0; 0; 0; 1000; 600; 150). Приведение задачи к каноническому виду: Примем за базисные переменные x 5, x 6, x 7. Тогда опорное решение: (0; 0; 0; 0; 1000; 600; 150).

25 Пример. 1 шаг симплекс-метода. Базисbibi ,54 x5x5 x6x6 x7x7 x1x1 x2x2 x3x3 x4x4 0x5x x6x x7x ,5-4

26 Пример. 1 шаг симплекс-метода Базисное решение (0; 0; 0; 0; 1000; 600; 150). Поиск ключевой строки: Выводим из базиса переменную x 7 и вводим переменную x 1 Базисное решение (0; 0; 0; 0; 1000; 600; 150). Поиск ключевой строки: Выводим из базиса переменную x 7 и вводим переменную x 1

27 Пример. 2 шаг симплекс-метода. Базисbibi ,54 x5x5 x6x6 x7x7 x1x1 x2x2 x3x3 x4x4 0x5x x6x x1x ,52

28 Пример. 2 шаг симплекс-метода Базисное решение (150; 0; 0; 0; 250; 0; 0). Определение ключевой строки: Выводим из базиса переменную x 6 и вводим переменную x 2. Базисное решение (150; 0; 0; 0; 250; 0; 0). Определение ключевой строки: Выводим из базиса переменную x 6 и вводим переменную x 2.

29 Пример. 3 шаг симплекс-метода. БазисBiBi ,54 X5X5 X6X6 X7X7 X1X1 x2x2 x3x3 x4x4 0x5x , ,5 2x2x2 000, ,5 6x1x ,5

30 Пример. 3 шаг симплекс-метода Базисное решение (150; 0; 0; 0; 250; 0; 0). Определение ключевой строки: Выводим из базиса переменную x 1 и вводим переменную x 4. Базисное решение (150; 0; 0; 0; 250; 0; 0). Определение ключевой строки: Выводим из базиса переменную x 1 и вводим переменную x 4.

31 Пример. 4 шаг симплекс-метода. Базисbibi ,54 x5x5 x6x6 x7x7 x1x1 x2x2 x3x3 x4x4 0x5x ,5-1,51, x2x ,5-0,51,5000 4x4x ,50

32 Пример. 4 шаг симплекс-метода Оптимальное решение: (0; 225; 0; 150; 475; 0; 0), при котором F max = То есть, для получения наибольшей прибыли, равной 1050 денежных единиц, предприятие должно выпустить 225 единиц продукции вида A2, 150 единиц продукции вида A4. Продукцию вида A1 и A3 производить не выгодно. При этом сырье типа II и III будет использовано полностью, а 475 единиц сырья типа I останутся неизрасходованными. Оптимальное решение: (0; 225; 0; 150; 475; 0; 0), при котором F max = То есть, для получения наибольшей прибыли, равной 1050 денежных единиц, предприятие должно выпустить 225 единиц продукции вида A2, 150 единиц продукции вида A4. Продукцию вида A1 и A3 производить не выгодно. При этом сырье типа II и III будет использовано полностью, а 475 единиц сырья типа I останутся неизрасходованными.

33 Метод искусственного базиса

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

35 Сущность метода Метод искусственного базиса: Полученная М-задача решается до получения оптимального плана. Если в оптимальном плане М-задачи значения искусственных переменных равны нулю, то значения остальных компонент образуют оптимальный план исходной задачи. Если в оптимальном плане М-задачи значение хотя бы одной из искусственных переменных отлично от нуля, то исходная задача не имеет ни одного плана (ее ограничения противоречивы). Метод искусственного базиса: Полученная М-задача решается до получения оптимального плана. Если в оптимальном плане М-задачи значения искусственных переменных равны нулю, то значения остальных компонент образуют оптимальный план исходной задачи. Если в оптимальном плане М-задачи значение хотя бы одной из искусственных переменных отлично от нуля, то исходная задача не имеет ни одного плана (ее ограничения противоречивы).

36 Сущность метода Метод искусственного базиса: В ограничения добавляют неотрицательные искусственные переменные таким образом, чтобы возникла единичная подматрица коэффициентов. Эти переменные составляют исходный базис задачи. Искусственные переменные включают в целевую функцию с коэффициентом - М (для задачи максимизации), где М > 0 - сколь угодно большое число. Метод искусственного базиса: В ограничения добавляют неотрицательные искусственные переменные таким образом, чтобы возникла единичная подматрица коэффициентов. Эти переменные составляют исходный базис задачи. Искусственные переменные включают в целевую функцию с коэффициентом - М (для задачи максимизации), где М > 0 - сколь угодно большое число.

37 Пример Исходная задача:

38 Пример М-задача:

39 Пример М-задача с преобразованной целевой функцией:

40 Пример Симплекс-таблица. 1 шаг. с Базис bibi 4-42-M X1X1 x2x2 x3x3 x4x4 x5x5 -Мx4x x5x j-3M-4M-44-3M-200

41 Пример Симплекс-таблица. 2 шаг. с Базис bibi 4-42-M x1x1 x2x2 x3x3 x4x4 x5x5 4x1x1 1/21 ½0 -Мx5x j-M+202M+6-M2M+20

42 Пример Симплекс-таблица. 3 шаг. Решение: x = (0,0,1); F(x) = 2 Симплекс-таблица. 3 шаг. Решение: x = (0,0,1); F(x) = 2 с Базис bibi 4-42-M x1x1 x2x2 x3x3 x4x4 x5x5 4x1x1 011,501-0,5 2x3x j2060M+2M

43 Теория двойственности и ее экономическая интерпретация

44 Исходная задача линейного программирования Целевая функция: Ограничения: и Целевая функция: Ограничения: и

45 Двойственная задача линейного программирования Целевая функция: Ограничения: и Целевая функция: Ограничения: и

46 Правила составления двойственной задачи 1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной – на минимум. 2. Матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием. 1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной – на минимум. 2. Матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием.

47 Правила составления двойственной задачи 3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче. 4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи. 3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче. 4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи.

48 Правила составления двойственной задачи 5. Если переменная x j исходной задачи может принимать только положительные значения, то j–е условие в системе двойственной задачи является неравенством вида «». Если же переменная x j может принимать как положительные, так и отрицательные значения, то j – соотношение в системе ограничений двойственной задачи представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Двойственная пара задач называется симметричной, если ограничения прямой задачи и соотношения двойственной задачи являются неравенствами. 5. Если переменная x j исходной задачи может принимать только положительные значения, то j–е условие в системе двойственной задачи является неравенством вида «». Если же переменная x j может принимать как положительные, так и отрицательные значения, то j – соотношение в системе ограничений двойственной задачи представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Двойственная пара задач называется симметричной, если ограничения прямой задачи и соотношения двойственной задачи являются неравенствами.

49 Пример Исходная задача: Двойственная задача: Найти максимум Найти минимум при условиях при условиях Исходная задача: Двойственная задача: Найти максимум Найти минимум при условиях при условиях

50 Зависимости между решениями прямой и двойственной задачи 1. Если Х – некоторый план исходной задачи, a Y – произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y. 2. Если для некоторых планов X* и Y* двойственной пары задач, то X* – оптимальный план исходной задачи, а Y* – оптимальный план двойственной задачи. 1. Если Х – некоторый план исходной задачи, a Y – произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y. 2. Если для некоторых планов X* и Y* двойственной пары задач, то X* – оптимальный план исходной задачи, а Y* – оптимальный план двойственной задачи.

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

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

53 Экономическая интерпретация Ресурсы, которые при оптимальном плане используются полностью, имеют положительную двойственную оценку. Величина двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества соответствующего ресурса на единицу. Ресурсы, которые в оптимальном плане используются не полностью, имеют двойственную оценку, равную 0. Ресурсы, которые при оптимальном плане используются полностью, имеют положительную двойственную оценку. Величина двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества соответствующего ресурса на единицу. Ресурсы, которые в оптимальном плане используются не полностью, имеют двойственную оценку, равную 0.