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

Необходимо определить оптимальный план производства продукции, при котором прибыль была бы максимальной.

Составить экономико-математическую модель задачи и двойственную к ней. Решить задачу симплексным методом. Проанализировать полученное решение с использованием свойств двойственных оценок.

Решение задачи находим с помощью калькулятора "Двойственные оценки".

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 9x₁ + 13x₂ + 11x₃ + 12x₄ при следующих условиях-ограничений.
2x₁ + 2x₂ + 2x₃ + x₄≤30
x₁ + x₂ + 5x₃ + x₄≤30
x₂ + 4x₃ + 2x₄≤25
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x₅. В 2-м неравенстве смысла (≤) вводим базисную переменную x₆. В 3-м неравенстве смысла (≤) вводим базисную переменную x₇.
2x₁ + 2x₂ + 2x₃ + 1x₄ + 1x₅ + 0x₆ + 0x₇ = 30
1x₁ + 1x₂ + 5x₃ + 1x₄ + 0x₅ + 1x₆ + 0x₇ = 30
0x₁ + 1x₂ + 4x₃ + 2x₄ + 0x₅ + 0x₆ + 1x₇ = 25

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x₅, x₆, x₇
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,30,30,25)
Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2
и из них выберем наименьшее:
min (30 : 2 , 30 : 1 , 25 : 1 ) = 15
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x₅ в план 1 войдет переменная x₂.
Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x₂ плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

Получаем новую симплекс-таблицу:

Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x₄, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i4
и из них выберем наименьшее:
min (15 : ¹/₂ , 15 : ¹/₂ , 10 : 1¹/₂ ) = 6²/₃
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (1¹/₂) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x₇ в план 2 войдет переменная x₄.
Строка, соответствующая переменной x₄ в плане 2, получена в результате деления всех элементов строки x₇ плана 1 на разрешающий элемент РЭ=1¹/₂
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x₄ плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x₄ и столбец x₄.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

Получаем новую симплекс-таблицу:

1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:

Оптимальный план можно записать так:
x₂ = 11²/₃
x₄ = 6²/₃
F(X) = 13•11²/₃ + 12•6²/₃ = 231²/₃

Построим двойственную задачу по следующим правилам.
1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.
2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.
Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
Расширенная матрица A.

Транспонированная матрица A^T.

Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
Неравенства, соединенные стрелочками (↔), называются сопряженными.
2y₁ + y₂≥9
2y₁ + y₂ + y₃≥13
2y₁ + 5y₂ + 4y₃≥11
y₁ + y₂ + 2y₃≥12
30y₁ + 30y₂ + 25y₃ → min
y₁ ≥ 0
y₂ ≥ 0
y₃ ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A^-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:
y₁ = 4²/₃
y₂ = 0
y₃ = 3²/₃
Z(Y) = 30*4²/₃+30*0+25*3²/₃ = 231²/₃

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
2*0 + 2*11²/₃ + 2*0 + 1*6²/₃ = 30 = 30
1*0 + 1*11²/₃ + 5*0 + 1*6²/₃ = 18¹/₃ < 30
0*0 + 1*11²/₃ + 4*0 + 2*6²/₃ = 25 = 25
1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁>0).
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y₂ = 0.
Неиспользованный экономический резерв ресурса 2 составляет 11²/₃ (30-18¹/₃).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₃>0).
Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными, (они будут иметь самые высокие оценки), какие менее дефицитными и какие совсем недефицитны (избыточны) - они будут равны нулю.
Обоснование эффективности оптимального плана.
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
2*4²/₃ + 1*0 + 0*3²/₃ = 9¹/₃ > 9
2*4²/₃ + 1*0 + 1*3²/₃ = 13 = 13
2*4²/₃ + 5*0 + 4*3²/₃ = 24 > 11
1*4²/₃ + 1*0 + 2*3²/₃ = 12 = 12
1-ое ограничение выполняется как строгое неравенство, т.е. продукцию 1-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₁ = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (9¹/₃ - 9 = ¹/₃) показывает величину изменения целевой функции F(x) при введении дополнительной единицы x_i.
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый продукт экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₂>0).
3-ое ограничение выполняется как строгое неравенство, т.е. продукцию 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₃ = 0.
Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.
При этом разница между ценами (24 - 11 = 13) показывает величину изменения целевой функции F(x) при введении дополнительной единицы x_i.
4-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 4-ый продукт экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x₄>0).
Решение было получено и оформлено с помощью сервиса:
Двойственная задача линейного программирования
Вместе с этой задачей решают также:
Задачи динамического программирования онлайн
Графический метод решения задач линейного программирования
Двойственный симплекс-метод
Теория игр онлайн
Метод Гомори
Транспортная задача
Расчет сетевого графика
Теория массового обслуживания онлайн