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

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

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

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

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

5 1. Приведение задачи к каноническому виду Для приведения задачи к каноническому виду необходимо добавить в каждое из ограничений задачи, представленных неравенствами, по одной переменной. Например: Неканонический вид: Канонический вид:. Для приведения задачи к каноническому виду необходимо добавить в каждое из ограничений задачи, представленных неравенствами, по одной переменной. Например: Неканонический вид: Канонический вид:.

6 2. Приведение задачи к допустимому виду Для того, чтобы привести систему уравнений к допустимому виду, необходимо выразить любые m неизвестных через остальные: b i 0 Для того, чтобы привести систему уравнений к допустимому виду, необходимо выразить любые m неизвестных через остальные: b i 0

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

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

9 2. Преобразование целевой функции Получим: или где. Получим: или где.

10 3. Нахождение первого допустимого базисного решения Приравняем свободные переменные к нулю и найдем значения базисных переменных. Получим одно из базисных решений системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если значения базисных переменных в нем неотрицательны. Приравняем свободные переменные к нулю и найдем значения базисных переменных. Получим одно из базисных решений системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если значения базисных переменных в нем неотрицательны.

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

12 4. Проверка решения на оптимальность Допустимое базисное решение системы ограничений является оптимальным решением задачи линейного программирования тогда и только тогда, когда все j 0. Если все j строго положительны, то решение является единственным. Допустимое базисное решение системы ограничений является оптимальным решением задачи линейного программирования тогда и только тогда, когда все j 0. Если все j строго положительны, то решение является единственным.

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

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

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

16 Симплекс-таблица: развернутый вариант Базис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 …n

17 Симплекс-таблица: сокращенный вариант Базисbibi c m+1 …cncn x m+1 …xnxn c1c1 x1x1 b1b1 a 1m+1 …a 1n c2c2 x2x2 b2b2 a 2m+1 …a 2n ……………… cmcm xmxm bmbm a mm+1 …a mn m+1 …n

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

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

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

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

22 Симплекс-таблица: алгоритм решения 4 а) в обозначениях строк и столбцов переменная, вводимая в базис и переменная, выводимая из него, меняются местами; 4 б) на месте ключевого элемента записываем обратное ему число; 4 в) ключевую строку (за исключением ключевого элемента) делим на ключевой элемент; полученную строку вписываем на место ключевой; 4 г) ключевой столбец (за исключением ключевого элемента) делим на ключевой элемент с противоположным знаком; полученный столбец вписываем на место ключевого; 4 а) в обозначениях строк и столбцов переменная, вводимая в базис и переменная, выводимая из него, меняются местами; 4 б) на месте ключевого элемента записываем обратное ему число; 4 в) ключевую строку (за исключением ключевого элемента) делим на ключевой элемент; полученную строку вписываем на место ключевой; 4 г) ключевой столбец (за исключением ключевого элемента) делим на ключевой элемент с противоположным знаком; полученный столбец вписываем на место ключевого;

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

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

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

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

27 Пример Приведение задачи к каноническому виду: Примем за базисные переменные 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).

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

29 Пример. 1 шаг симплекс-метода, сокращенная таблица. Базисbibi 622,54 x1x1 x2x2 x3x3 x4x4 0x5x x6x x7x ,5-4

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

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

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

33 Пример. 3 шаг симплекс-метода. БазисBiBi 002,54 X7X7 X6X6 x3x3 x4x4 0x5x ,5-7-1,5 2x2x ,5-3-1,5 6x1x ,5

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

35 Пример. 4 шаг симплекс-метода. Базисbibi 002,56 x7x7 x6x6 x3x3 x1x1 0x5x ,5-0,5-41,5 2x2x ,50,501,5 4x4x ,51

36 Пример. 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 останутся неизрасходованными.