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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Правила составления двойственной задачи 3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче.

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

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

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

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

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

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

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

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

Пример Математическая модель прямой задачи: y 1 y 2 y 3. Математическая модель прямой задачи: y 1 y 2 y 3.

Пример Двойственная задача: F* = 1000y y y 3 min 5y 1 + 4y 2 + y 3 6 y 1 + 2y 2 2 2y 2 + 2y 3 2,5 2y 1 + y 2 + y 3 4 y i 0, i = 1,2,3,4 Двойственная задача: F* = 1000y y y 3 min 5y 1 + 4y 2 + y 3 6 y 1 + 2y 2 2 2y 2 + 2y 3 2,5 2y 1 + y 2 + y 3 4 y i 0, i = 1,2,3,4

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

Пример. Решение прямой задачи Оптимальное решение: (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 останутся неизрасходованными.

Пример. Решение двойственной задачи Оптимальное решение: (0; 1; 3), при котором F* min = Двойственные оценки сырья показывают, что первый сырье первого вида используется не полностью, а сырье второго и третьего вида находится в дефиците. При этом увеличение на 1 единицу запасов сырья второго вида приведет к увеличению прибыли фирмы на 1 единицу, а увеличение на 1 единицу запасов сырья третьего вида увеличит прибыль фирмы на 3 единицы. Оптимальное решение: (0; 1; 3), при котором F* min = Двойственные оценки сырья показывают, что первый сырье первого вида используется не полностью, а сырье второго и третьего вида находится в дефиците. При этом увеличение на 1 единицу запасов сырья второго вида приведет к увеличению прибыли фирмы на 1 единицу, а увеличение на 1 единицу запасов сырья третьего вида увеличит прибыль фирмы на 3 единицы.