Симплекс-метод. Анализ чувствительности изменения коэффициентов целевой функции

Задача 14. Магазин В&К продает два вида безалкогольных напитков: колу А₁ известного производителя и колу В&К собственного производства. Доход от одной банки колы А₁ составляет 5 центов, тогда как доход от одной банки собственной колы — 7 центов. В среднем магазин за день продает не более 500 банок обоих напитков. Несмотря на то что А₁ известная торговая марка, покупатели предпочитают колу В&К, поскольку она значительно дешевле. Подсчитано, что объемы продаж колы В&К и А₁ (в натуральном исчислении) должны соотноситься не менее 2:1. Кроме того, известно, что магазин продает не менее 100 банок колы А₁ в день.

а) Сколько банок каждого напитка должен иметь магазин в начале рабочего дня для максимального дохода?

b) Провести анализ чувствительности изменения коэффициентов целевой функции.

с) Провести анализ чувствительности запасов сырьевых ресурсов, определяющих оптимальное решение.

d) Сделать выводы и записать рекомендации.

Решение:

а)  Симплекс-метод.

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 5x₁+7x₂ при следующих условиях-ограничений.
x₁+x₂≤500
x₁≥100
-2x₁+x₂≥0
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≥) вводим базисную переменную x₄ со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус.
x₁+x₂+x₃ = 500
x₁-x₄ = 100
-2x₁+x₂-x₅ = 0
Расширенная матрица системы ограничений-равенств данной задачи:

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
Получаем новую матрицу:

3. В качестве базовой переменной можно выбрать x₅.
Получаем новую матрицу:

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Выразим базисные переменные через остальные:
x₃ = -x₁-x₂+500
x₄ = x₁-100
x₅ = -2x₁+x₂
Подставим их в целевую функцию:
F(X) = 5x₁+7x₂
Среди свободных членов b_i имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x₄ следует ввести переменную x₁.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Представим расчет каждого элемента в виде таблицы:

Среди свободных членов b_i имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x₅ следует ввести переменную x₂.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Представим расчет каждого элемента в виде таблицы:

Выразим базисные переменные через остальные:
x₃ = -3x₄-x₅+200
x₁ = x₄+100
x₂ = 2x₄+x₅+200
Подставим их в целевую функцию:
F(X) = 5(x₄+100)+7(2x₄+x₅+200)
или
F(X) = 19x₄+7x₅+1900
x₃+3x₄+x₅=200
x₁-x₄=100
x₂-2x₄-x₅=200
При вычислениях значение Fc = 1900 временно не учитываем.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x₃, x₁, x₂
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (100,200,200,0,0)
Базисное решение называется допустимым, если оно неотрицательно.

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

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

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

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

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

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

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

Оптимальный план можно записать так:
x₁ = 100, x₂ = 400
F(X) = 5*100 + 7*400 = 3300

b) Изменение значений коэффициентов c₁ и c₂ приводит к изменению угла наклона прямой z. Существует интервалы изменения коэффициентов c₁ и c₂, когда текущее оптимальное решение сохраняется. Задача анализа чувствительности и состоит в получении такой информации. Необходимо определить интервал оптимальности для отношения c₁ / c₂ (или c₂ и c₁). Если значение отношения c₁ / c₂ не выходит за пределы этого интервала, то оптимальное решение в данной модели сохраняется неизменным.
Таким образом, в рамках анализа на чувствительность к изменениям коэффициентов целевой функции могут исследоваться вопросы:
1. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения.
2. На сколько следует изменить тот или иной коэффициент целевой функции, чтобы изменить статус некоторого ресурса.
На предыдущем рисунке видно, что функция достигает своего оптимума в точке, которая является пересечением прямых (x₁+x₂=500) и (x₁=100). При изменении коэффициентов целевой функции эта точка останется точкой оптимального решения до тех пор, пока угол наклона линии z будет лежать между углами наклона этих прямых. Алгебраически это можно записать следующим образом:

при условии c₁ ≠ 0
или

при условии c₂ ≠ 0
Таким образом, мы получили две системы неравенств, определяющих интервал оптимальности.
При c₂ = 7

или
0 ≤ c₁ ≤ 7
При c₁ = 5

или
0 ≤ c₂ ≤ 5

с) На данном этапе важно проанализировать следующие аспекты:
1. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции.
2. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции.
Оценка ресурса M1
Концевые точки отрезка определяют интервал осуществимости для ресурса M1.
Количество сырья, соответствующего точке (100,200), равно 1·100 + 1·200 = 300
Таким образом, интервал осуществимости для ресурса M1 составляет ≤ M1 ≤ 300
Вычислим значение целевой функции в этих точках:
F(100,200) = 5·100 + 7·200 = 1900


Изменение области решений при увеличении запасов ресурса M1
Оценка ресурса M2
Концевые точки отрезка определяют интервал осуществимости для ресурса M2.
Количество сырья, соответствующего точке (166.667,333.333), равно 1·166.667 + 0·333.333 = 166.667
Количество сырья, соответствующего точке (0,500), равно 1·0 + 0·500 = 0
Таким образом, интервал осуществимости для ресурса M2 составляет 0 ≤ M2 ≤ 166.667
Вычислим значение целевой функции в этих точках:
F(166.667,333.333) = 5·166.667 + 7·333.333 = 3166.667
F(0,500) = 5·0 + 7·500 = 3500


Изменение области решений при увеличении запасов ресурса M2
Рассмотрим теперь вопрос об уменьшении правой части неактивного ограничения (3). Не изменяя оптимального решения, прямую L3 можно опустить до пересечения с оптимальной точкой. При этом правая часть ограничения (3) станет равной -2x₁+x₂=200, что позволит записать ограничение (1) в виде -2x₁+x₂≥200.
y_i определяет ценность каждой дополнительной единицы дефицитного ресурса. Чем больше значение y_i, тем выше его приоритет при вложении дополнительных средств.

d) В оптимальный план вошла дополнительная переменная x₅. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 200.

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