Основы исследования операций (стр. 9 )

Рассмотрим вопрос об уменьшении запасов "недефицитных" ресурсов. В нашем примере таким ресурсом является краситель к3 (прямаяLE). Уменьшению объема использования ресурса к3 соответствует движение прямой LE параллельно самой себе в сторону начала координат. При уменьшении на единицу эта прямая будет проходить через точку В. Это не повлияет на оптимальное решение (по прежнему в точке С). Границе допустимого интервала уменьшения запасов ресурса к3 соответствует сдвиг прямой до точкиС (до точки оптимального решения), при этом ресурс к3приобретает статус "дефицитного". Уравнение ограничивающей прямой, соответствующей ресурсу к3, будет то есть возможно уменьшение запасов ресурса к3на 5/3 без изменения оптимального решения.

7. ПОСЛЕОПТИМИЗАЦИОННЫЙ АНАЛИЗ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

а) изменение коэффициентов вектора ограничений bi;

б) изменение коэффициентов целевой функции;

в) изменение технологических коэффициентов;

д) добавление новой переменной;

г) добавление нового ограничения.

Первая из этих задач рассмотрена в предыдущем разделе.

7.1. Изменение коэффициентов целевой функции

Рассмотрим влияние на оптимальное решение изменения коэффициентов целевой функции при базисной переменной. Изменение cj на величину ведет к изменению оценок всех свободных переменных в соответствии со следующим выражением:

Для того, чтобы решение оставалось оптимальным, должно выполняться условие т. е.

где – относительная оценка, соответствующая текущему оптимальному решению.

В общем, эффект от изменения коэффициентов целевой функции можно рассматривать с двух позиций:

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

–  с точки зрения сбыта нас интересуют равновесные цены.

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

	cj	3	2+Dc2	0	0	0	0
	БП	x1	x2	x3	x4	x5	x6
2+Dc2	x2	0	1	2/3	–1/3	0	0	4/3
3	x1	1	0	–1/3	2/3	0	0	10/3
0	x5	0	0	–5/3	1/3	1	0	5/3
0	x6	0	0	–2/3	1/3	0	1	2/3
	F	0	0	2/3Dc2+1/3	–1/3Dc2+4/3	0	0	38/3+4/3Dc2

Тогда условие оптимальности запишется следующим образом:

Интервал устойчивости решения

Итак, если оптовая цена на краску П2 будет меняться от 3/2 до 6 млн. рублей за 1 т, полученное выше решение все равно будет оптимальным.

Рассмотрим влияние изменения коэффициента целевой функции при небазисной (свободной) переменной. Пусть коэффициент целевой функции изменился на величину d; Тогда относительная оценка изменится в соответствии с формулой

Условие оптимальности плана будет иметь вид:

Диапазон устойчивости, в котором cj может меняться так, чтобы текущее решение оставалось оптимальным, задается выражением:

Отметим, что при любом отрицательном d относительная оценка этой переменной останется положительной.

7.2. Изменение технологических коэффициентов

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

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

Обычно рассматривают изменения коэффициентов матрицы, отвечающих только небазисным (свободным) переменным. Изменение технологического коэффициента aij при свободной переменной xj влечет изменение оценки только этой свободной переменной на величину

Условие оптимальности плана, как и ранее, будет иметь следующий вид:

Из этого соотношения в каждом конкретном случае определяется условие устойчивости решения к изменению технологического коэффициента.

В рассмотренном нами примере обе переменные x1 и x2 являются базисными.

7.3. Введение новой переменной

Оценим целесообразность включения в план изготовления третьего вида краски П3. Для ее изготовления также используются три красителя к1, к2,к3 с затратами 3, 2, 1 кг/т соответственно. Оптовая цена на краску П3 составляет 4 млн. рублей за 1т.

Введем новую переменную – количество краски П3, выпускаемой химическим комбинатом. Тогда математическая модель задачи запишется в виде:

Введение новой переменной в прямой задаче означает, что в двойственной задаче появляется новое ограничение.

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

, значит полученное ранее решение не оптимально.

Найдем новое оптимальное решение используя последнюю симплекс-таблицу прямой задачи. Столбец определяется следующим образом:

Матрицу B-1 берем из последней симплекс-таблицы:

Теперь записываем симплекс-таблицу:

	cj	3	2	0	0	0	0	4
	БП	x1	x2	x3	x4	x5	x6	x3'
2	x2	0	1	2/3	–1/3	0	0	4/3	4/3
3	x1	1	0	–1/3	2/3	0	0	1/3	10/3
0	x5	0	0	–5/3	1/3	1	0	–10/3	5/3
0	x6	0	0	–2/3	1/3	0	1	–4/3	2/3
	F	0	0	1/3	4/3	0	0	–1/3	38/3
4	x3'	0	3/4	1/2	–1/4	0	0	1	1
3	x1	1	–1/4	–1/2	3/4	0	0	0	3
0	x5	0	7/2	2/3	5/6	1	0	0	5
0	x6	0	1	0	0	0	1	0	2
	F	0	1/4	1/2	5/4	0	0	0	13

Оптимальное решение будет: