Сетевое издание

Международный студенческий научный вестник

ISSN 2409-529X

Оптимальное решение задачи линейного программирования (ЛП) существенно зависит от реальной экономической ситуации, складывающейся на предприятии. На решение задачи могут повлиять следующие экономические ситуации [1, c. 247]:

1) изменение запасов ресурсов;

2) внедрение нового технологического способа производства, позволяющего снизить расход сырья А и В;

3) произошедшие изменения в ценовой политике на предприятии;

4) предполагается выпуск новой продукции.

Чтобы определить диапазон допустимых изменений параметров задачи (коэффициентов функции цели, системы ограничений). Которые не требуют изменения полученного оптимального решения, производят так называемый анализ полученного решения на чувствительность. Кроме того. Такой анализ показывает, какие параметры могут улучшить или ухудшить найденное решение [2, c. 89].

В данной работе мы предлагаем рассмотрение процедуры анализа полученного оптимального решения задачи ЛП на чувствительность.

Процедуру анализа решения удобно рассмотреть на примере графического решения задачи.

Пример графического решения задачи.

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

Задача.

,

Решение.

1. Решим данную задачу графическим методом.

Введем на плоскости прямоугольную систему координат и построим область допустимых решений (ОДР) задачи.

Рассмотрим первое неравенство системы ограничений:

.

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

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

Полагая, что , получим ; полагая, что , получим . Следовательно, искомая прямая проходит через точки (0;2,5) и (7,5;0). Построим данную прямую, обозначив её римской цифрой I (рис.1).

Для нахождения искомой полуплоскости испытаем начало координат О(0;0). Получим . Таким образом, искомая полуплоскость расположена по ту же сторону от прямой, что и начало координат. Отметим этот факт стрелочкой на прямой.

Рассмотрим второе неравенство системы ограничений: .

Уравнение границы полуплоскости: .

Полагая, что , получим ; полагая, что , получим . Следовательно, искомая прямая проходит через точки (0; 3,67) и (2,75; 0). Построим данную прямую, обозначив её римской цифрой II (рис.1).

Для испытания выбираем начало координат. Получим . Следовательно, искомая полуплоскость расположена по ту же сторону от прямой, что и начало координат. Отметим этот факт стрелочкой.

Рис.1. Геометрическая интерпретация задачи.

Находим ОДР задачи как пересечение найденных полуплоскостей. Легко увидеть, что это будет выпуклый многоугольник OABC.

Построим направляющий вектор , начало которого - в начале координат, коней - в точке (2,1) (см. Рис.1). Проведем линию одного уровня функции цели перпендикулярно направляющему вектору и будем смещать её параллельно самой себе в направлении, указываемом вектором (при отыскании максимума целевой функции) до тех пор, пока она будет иметь одну общую точку с ОДР. На рисунке можно увидеть, что такой точкой будет точка С (см. Рис.1.). Следовательно, в точке С достигается максимум целевой функции. Координаты точки С: , . Соответствующее максимальное значение целевой функции:

.

Решение задачи записываем так: ; .

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

2.1. Анализ целевой функции.

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

Предположим, что величина цены единицы второго вида продукции, которая выпускается предприятием, уменьшается, а величина цены единицы первого вида продукции - увеличивается. Эти изменения коэффициентов целевой функции влекут изменение направления вектора . Очевидно, что направляющий вектор будет разворачиваться по часовой стрелке к оси (см. Рис. 1). Поэтому линия одного уровня целевой функции (пунктирная линия) в точке оптимума С будет также поворачиваться по часовой стрелке.

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

Аналогично, при уменьшении величины коэффициента и увеличении значения коэффициента направляющий вектор будет разворачиваться против часовой стрелки к оси , то есть угол α, образуемый вектором с осью , будет возрастать, а линия одного уровня целевой функции в точке оптимума С будет поворачиваться также против часовой стрелки. Ясно, что текущее оптимальное решение не изменится до совпадения линии с прямой II, определяемой уравнением . Такое совпадение произойдет, когда направляющий вектор будет перпендикулярным к указанной прямой, или когда тангенсы угла наклона линии одного уровня целевой функции и заданной уравнением прямой совпадут.

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

. (1)

Здесь коэффициент при переменной равен тангенсу угла наклона этой линии к оси , а значение величины равно 5,5. Так как вектор перпендикулярен линии (1), то тангенс угла α наклона вектора к оси , равен (см. Рис.2):

.

Рис.2.

С другой стороны, уравнение прямой , разрешенное относительно переменной , примет вид: .

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

Таким образом, тангенс угла наклона α вектора изменяется в пределах:

или . (2)

Итак, получено условие неизменности оптимального решения задачи при изменении коэффициентов целевой функции. Решение остаётся неизменным, если отношение коэффициентов удовлетворяет соотношению (2).

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

. (3)

Рассмотрим два предельных случая.

1) Пусть выполняется левая часть неравенства (2), то есть полагаем . Тогда равно нулю и из (3) находим .

2) Пусть теперь выполняется правая часть неравенства (2), тогда полагаем . Тогда

. (4)

Подставив (4) в (3), получим: или .

Следовательно, .

Таким образом:

,

.

Итак, величина цены единицы первого вида продукта остаётся неизменной, а цена единицы второго продукта может изменяться от 0 до 1,5 д.е. и при этих изменениях оптимум задачи сохраняется.

2.2. Анализ изменений объема ресурсов.

Обычно при анализе изменений объема ресурсов исследуются две проблемы:

1) Какие изменения объемов используемых ресурсов не изменяет полученного экстремального значения целевой функции?

2) Какие изменения объемов используемых ресурсов увеличит полученное экстремальное значение целевой функции?

Критическими (дефицитными) называют ресурсы, которые в оптимальном решении используются полностью. Остальные ресурсы называют некритическими (недефицитными).

Очевидно, что критическими являются ресурсы, которые определяют точку оптимума. В нашей задаче это ограничение по второму ресурсу, определяемое уравнением . Пересечение этой прямой с осью определяет точку оптимального решения (Рис.1).

Рассмотрим вопрос об изменениях объемов ресурсов, не изменяющих экстремум целевой функции. Ясно, что изменения некритического ресурса не изменит экстремального значения целевой функции в некотором диапазоне. В нашей задаче это ограничение по первому ресурсу, описываемое уравнением , которое фиксирует предельный уровень спроса по первому ресурсу при неизменности максимального значения целевой функции. Из рисунка 1 следует, что, не изменяя максимального значения целевой функции, прямую I можно опустить вниз (уменьшать запасы по первому ресурсу) до пересечения с оптимальной точкой С, которая имеет координаты и . Этот запас становится критическим. Определим величину этого запаса: . Этот результат показывает, что ранее полученное оптимальное решение не изменяется, если запас первого ресурса уменьшается на 10 единиц.

Изменение критического ресурса изменяет оптимальное решение задачи. Следовательно, изменяется экстремум целевой функции. Рассмотрим это изменение.

Из рис. 1 следует, что, изменяя максимальное значение целевой функции, прямую II можно поднимать вверх (увеличивать запасы по первому ресурсу) до пересечения с точкой D, которая имеет координаты: и . Функция цели примет значение:

.

Величина рассматриваемого ресурса в точке D равна:

.

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

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