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

Задача 29. Фирма «Television» производит два вида телевизоров: «Астро» и «Космо».

В цехе 1 производят телевизионные трубки. На производство одной трубки к телевизору «Астро» требуется потратить 1,2 человекочаса, а на производство трубки к «Космо» — 1,8 человекочаса. В настоящее время в цехе 1 на производство трубок к обеим мар­кам телевизоров может быть затрачено не более 120 человекочасов в день.

В цехе 2 производят шасси с электронной схемой телевизора. На производство шасси для телевизора любой марки требуется затратить 1 человекочас. На производство шасси к обеим маркам телевизоров в цехе 2 может быть затрачено не более 90 человеко-часов в день.

Продажа каждого телевизора марки «Астро» обеспечивает при­быль в размере 1500 руб., а марки «Космо» — 2000 руб. Фирма заинтересована в максимизации прибыли.

а) Какова максимальная ежедневная прибыль компании.

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

с) Произвести анализ чувствительности запасов сырьевых ресурсов.

d) На сколько рублей в день увеличится прибыль, если ресурс времени в цехе 2 возрастет на 5 человеко/часов?

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

Решение:

а) Какова максимальная ежедневная прибыль компании.

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 1500x₁+2000x₂ при следующих условиях-ограничений.
x₁+x₂≤90
1.2x₁+1.8x₂≤120
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄.
x₁+x₂+x₃ = 90
1.2x₁+1.8x₂+x₄ = 120
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

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

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

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

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

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

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

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

Оптимальный план можно записать так:
x₁ = 70, x₂ = 20
F(X) = 1500*70 + 2000*20 = 145000
Анализ оптимального плана.
Значение 0 в столбце x₁ означает, что использование x₁ - выгодно.
Значение 0 в столбце x₂ означает, что использование x₂ - выгодно.
Значение 500 в столбце x₃ означает, что теневая цена (двойственная оценка) равна y₁=500.
Значение 833.333 в столбце x₄ означает, что теневая цена (двойственная оценка) равна y₂=833.333.

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

Изменение значений коэффициентов c₁ и c₂ приводит к изменению угла наклона прямой z. Существует интервалы изменения коэффициентов c₁ и c₂, когда текущее оптимальное решение сохраняется. Задача анализа чувствительности и состоит в получении такой информации. Необходимо определить интервал оптимальности для отношения c₁ / c₂ (или c₂ и c₁). Если значение отношения c₁ / c₂ не выходит за пределы этого интервала, то оптимальное решение в данной модели сохраняется неизменным.
Таким образом, в рамках анализа на чувствительность к изменениям коэффициентов целевой функции могут исследоваться вопросы:

1. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения.

2. На сколько следует изменить тот или иной коэффициент целевой функции, чтобы изменить статус некоторого ресурса.

На предыдущем рисунке видно, что функция достигает своего оптимума в точке, которая является пересечением прямых (x₁+x₂=90) и (1.2x₁+1.8x₂=120). При изменении коэффициентов целевой функции эта точка останется точкой оптимального решения до тех пор, пока угол наклона линии z будет лежать между углами наклона этих прямых. Алгебраически это можно записать следующим образом:

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

или

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

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

При c₂ = 2000

или
1333.33 ≤ c₁ ≤ 2000

При c₁ = 1500

или
1500 ≤ c₂ ≤ 2250

Чувствительность решения к изменению коэффициентов целевой функции.

Так как любые изменения коэффициентов целевой функции оказывают влияние на оптимальность полученного ранее решения, то наша цель - найти такие диапазоны изменения коэффициентов в целевой функции (рассматривая каждый из коэффициентов отдельно), при которых оптимальные значения переменных остаются неизменными.
Пусть каждое значение параметра целевой функции изменится на ∆ с_i. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.

Допустимые диапазоны изменения коэффициентов в целевой функции определятся из соотношений:

Вариант расчета №1.

Отсюда получаем условие устойчивости:
3Δc₁-2Δc₂+500≥0

-1.67Δc₁+1.67Δc₂+833.33≥0

Затем последовательно находим интервалы устойчивости:

Δc₁≠0, Δc₂=0, Δc₁≥-166.67, Δc₁≤500

Δc₂≠0, Δc₁=0, Δc₂≤⁵⁰⁰/₂, Δc₂≥-500

Вариант расчета №2.

1-й параметр целевой функции может изменяться в пределах:

∆c₁^- = min [y_k/d_1k] для d_1k>0.

∆c₁⁺ = |max[y_k/d_1k]| для d_1k<0.

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

Таким образом, 1-й параметр может быть уменьшен на 166.67 или увеличен на 500.

Интервал изменения равен:

(c₁ - ∆c^-₁; c₁ + ∆c₁⁺)

[1500-166.67; 1500+500] = [1333.33;2000]

Если значение c₁ будет лежать в данном интервале, то оптимальный план не изменится.

2-й параметр целевой функции может изменяться в пределах:

∆c₂^- = min [y_k/d_2k] для d_2k>0.

∆c₂⁺ = |max[y_k/d_2k]| для d_2k<0.

Таким образом, 2-й параметр может быть уменьшен на 500 или увеличен на ⁵⁰⁰/₂.

Интервал изменения равен:

(c₂ - ∆c^-₂; c₂ + ∆c₂⁺)

[2000-500; 2000+⁵⁰⁰/₂] = [1500;⁴⁵⁰⁰/₂]

Если значение c₂ будет лежать в данном интервале, то оптимальный план не изменится.

с) Произвести анализ чувствительности запасов сырьевых ресурсов.

На данном этапе важно проанализировать следующие аспекты:

1. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции.

2. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции.

Оценка ресурса M1

Концевые точки отрезка определяют интервал осуществимости для ресурса M1.

Количество сырья, соответствующего точке (100,0), равно 1·100 + 1·0 = 100

Количество сырья, соответствующего точке (0,66.67), равно 1·0 + 1·66.67 = 66.67

Таким образом, интервал осуществимости для ресурса M1 составляет 66.67 ≤ M1 ≤ 100

Вычислим значение целевой функции в этих точках:

F(100,0) = 1500·100 + 2000·0 = 150000

F(0,66.67) = 1500·0 + 2000·66.67 = 133333.33

Чувствительность решения к изменению запасов сырья.

Из теоремы об оценках известно, что колебание величины b_i приводит к увеличению или уменьшению f(X).

Оно определяется величиной y_i в случае, когда при изменении величин b_i значения переменных у_i в оптимальном плане соответствующей двойственной задачи остаются неизменными.

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

Найдем интервалы устойчивости ресурсов.

Вариант расчета №1.
При этом условие устойчивости двойственных оценок задачи исходит из выражения:

X¹=X⁰+ΔX=A^-1(B+ΔB)
в которой компоненты вектора X¹ должны быть неотрицательны, т.е. все x_j≥0. На этом основании для нашей задачи можно записать:

Отсюда получаем условие устойчивости:

3Δb₁-1.67Δb₂+70≥0

-2Δb₁+1.67Δb₂+20≥0

Затем последовательно находим интервалы устойчивости:

Δb₁≠0, Δb₂=0, Δb₁≥^-70/₃, Δb₁≤²⁰/₂

Δb₂≠0, Δb₁=0, Δb₂≤42, Δb₂≥-12

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

Вариант расчета №2.

1-й запас может изменяться в пределах:

∆b₁^- = min[x_k/d_k1] для d_k1>0.\

∆b₁⁺ = |max[x_k/d_k1]| для d_k1<0.

Таким образом, 1-й запас может быть уменьшен на ⁷⁰/₃ или увеличен на ²⁰/₂.

Интервал изменения равен:

(b₁ - ∆b₁^-; b₁ + ∆b₁)⁺

[90-⁷⁰/₃; 90+²⁰/₂] = [66.67;²⁰⁰/₂]

2-й запас может изменяться в пределах:

∆b₂^- = min[x_k/d_k2] для d_k2>0.

∆b₂⁺ = |max[x_k/d_k2]| для d_k2<0.

Таким образом, 2-й запас может быть уменьшен на 12 или увеличен на 42.

Интервал изменения равен:

(b₂ - ∆b₂^-; b₂ + ∆b₂)⁺[120-12; 120+42] = [108;162]

Изменение области решений при увеличении запасов ресурса M1

Оценка ресурса M2

Концевые точки отрезка определяют интервал осуществимости для ресурса M2.

Количество сырья, соответствующего точке (0,90), равно 1.2·0 + 1.8·90 = 162

Количество сырья, соответствующего точке (90,0), равно 1.2·90 + 1.8·0 = 108

Таким образом, интервал осуществимости для ресурса M2 составляет 108 ≤ M2 ≤ 162

Вычислим значение целевой функции в этих точках:

F(0,90) = 1500·0 + 2000·90 = 180000

F(90,0) = 1500·90 + 2000·0 = 135000

Изменение области решений при увеличении запасов ресурса M2
y_i определяет ценность каждой дополнительной единицы дефицитного ресурса. Чем больше значение y_i, тем выше его приоритет при вложении дополнительных средств.

Теория двойственности.

Составим двойственную задачу к прямой задаче.

y₁+1.2y₂≥1500

y₁+1.8y₂≥2000

90y₁+120y₂ → min

y₁ ≥ 0

y₂ ≥ 0

Отметим, что решение двойственной задачи дает оптимальную систему оценок ресурсов.

Для решения двойственной задачи используем вторую теорему двойственности.

Подставим оптимальный план прямой задачи в систему ограниченной математической модели:

1*70 + 1*20 = 90 = 90

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₁ > 0).

1.2*70 + 1.8*20 = 120 = 120

2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y₂ > 0).

Поскольку x₁>0, первое ограничение в двойственной задаче будет равенством.

Поскольку x₁>0, второе ограничение в двойственной задаче будет равенством.

С учетом найденных оценок, новая система примет вид:

y₁+1.2y₂ = 1500

y₁+1.8y₂ = 2000

90y₁+120y₂ → min

Или

y₁+1.2y₂ = 1500

y₁+1.8y₂ = 2000

90y₁+120y₂ → min

Решая систему графическим способом, находим оптимальный план двойственной задачи:

Или

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

y₁+1.2y₂=1500

y₁+1.8y₂=2000

Решив систему уравнений, получим: y₁ = 500, y₂ = 833.3333

Откуда найдем минимальное значение целевой функции:

F(X) = 90*500 + 120*833.3333 = 145000

y₁ = 500

y₂ = 833.33

Z(Y) = 90*500+120*833.33 = 145000

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

Обоснование эффективности оптимального плана.

При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:

1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что продукт №1 экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x₁ > 0)

1*500 + 1.2*833.33 = 1500 = 1500

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что продукт №2 экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x₂ > 0)

1*500 + 1.8*833.33 = 2000 = 2000

d) На сколько рублей в день увеличится прибыль, если ресурс времени в цехе 2 возрастет на 5 человеко/часов?

Необходимо найти максимальное значение целевой функции F = 1500x₁+2000x₂ → max, при системе ограничений:

x₁+x₂≤95, (1)

1.2x₁+1.8x₂≤120, (2)

x₁ ≥ 0, (3)

x₂ ≥ 0, (4)

Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

или

Шаг №2. Границы области допустимых решений.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Обозначим границы области многоугольника решений.

Шаг №3. Рассмотрим целевую функцию задачи F = 1500x₁+2000x₂ → max.

Построим прямую, отвечающую значению функции F = 1500x₁+2000x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (1500;2000). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

x₁+x₂=95

1.2x₁+1.8x₂=120

Решив систему уравнений, получим: x₁ = 85, x₂ = 10
Откуда найдем максимальное значение целевой функции:

F(X) = 1500*85 + 2000*10 = 147500

147500 – 145000 = 2500

Таким образом, если ресурс времени в цехе 2 возрастет на 5 человеко/часов, то прибыль увеличится на 2500 рублей в день.

Можно сделать вывод,  что следует изменить план производства, т.к. производство одних только телевизоов «Космо» будет прибыльней, чем на данный момент.