Анализ устойчивости двойственных оценок

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

Составляем матрицу А из элементов столбцов, соответствующих переменных х₃, х₄, х₅ таблицы 7, определяющей оптимальный план производства:

A=

Умножаем матрицу на вектор B= , где 400, 900, 600 - запасы сырья, соответственно, 1, 2, 3-го видов; rp_j (j = 1, 2, 3) – предполагаемое изменение соответствующего вида сырья.

 

A•B= =

Записываем условие неотрицательности - компонент полученного вектора. (1.32)

Определим, при каких значениях rp₁, rp₂, rp₃ эта система неравенств верна. Очевидно, если rp₁ = rp₂ = 0, то rp₃ ≥ 100. Это означает, что если количество сырья 3-го вида будет уменьшено в пределах 100 кг или увеличено произвольным образом, то, несмотря на это, двойственные оценки сырья не изменятся.

Если rp₂ =rp₃ = 0, то решая систему (1.32), получим -100<rp₁ <200.

Если rp₁=rp₃ = 0, -300<rp₂ <100.

Это означает, что если количество одного из видов сырья 1-го или 2-го вида принадлежат соответственно промежуткам 300<rp₁ <600 или 600<rp₂ <1000, а количество остальных ресурсов остается первоначальным, то двойственные оценки сырья не меняются.

Если p₁, p₂ , p₃ изменяются одновременно, то для исследования влияния изменений на оптимальный план необходимо определить, принадлежат ли эти изменения rp₁, rp₂, rp₃ многоугольнику решений системы линейных неравенств (1.32). Точки этого многоугольника определяют количество сырья каждого вида, при котором двойственные оценки остаются прежними.

Предположим, что в рассматриваемой задаче изменения сырья составляют: rp₁ = 200 кг, rp₂ = 100 кг и rp₃ = 150 кг.

Определим, как при этом изменится оптимальный план, стоимость готовой продукции f и остатки сырья.

 

1-й способ. Подставим значения rp₁, rp₂, rp₃ в систему неравенств (1.32). Так как все неравенства остаются верными, это означает, что двойственные оценки сырья не изменятся. В этом случае изменение стоимости готовой продукции составит:

r f ₁= y ₁*r p ₁+ y ₂*r p ₂+ y ₃*r p ₃ = 24*200+ 4*100+ 0*(-150) = 5200 (д.ед.),

т.е. стоимость готовой продукции по новому оптимальному плану равна

f ₁=13200 + 5200 = 18400 (д.ед.).

Соответствующий план производства найдем следующим образом. Система ограничений, описывающая новые условия производства, примет вид: 2x₁+x₂ 600

3x₁+4x₂ 1000

X₁+3x₂ 450

X₁ 0, x₂ 0

Так как y ₁>0 и y ₂>0, то сырье 1-го и 2-го вида используется полностью. Поэтому 1-ое и 2-ое условия выполняются как равенство. Решая совместно систему 2 x ₁ + x ₂ = 600

3 x ₁ + 4 x ₂= 1000,

получим новый оптимальный план производства x ₁ = 280 ед.; x ₂ = 40 ед. При этом остатки сырья составят: x ₃ = x ₄ = 0, x ₅ = 50 кг.

Й способ.

Умножим матрицу А на вектор В= = . В соответствии с таблицей 7 получим вектор базисных решений: =AB=

Т. к. базисные решения допустимы (неотрицательны), то решение двойственной задачи не изменилось. Оптимальное значение f найдем, умножая строку теневых цен С = (24; 4; 0) на вектор В (напомним, что теневые цены – это решение двойственной задачи, которое находится под матрицей А в нижней строке таблицы 7).

f = CB = 24·600 + 4·1000 + 0·450 = 18400 (д.ед.).

Если при изменении объемов сырья меняются двойственные оценки, т.е. при подстановке rp₁, rp₂, rp₃ в систему (1.32) неравенства становятся неверными, то формулируется новая производственная задача, которая может быть решена описанным выше симплексным методом.

7. Решение задачи линейного программирования с по­мощью EXCEL

Рассмотрим задачу линейного программирования, сформулированную в п. З настоящей работы.

2x₁ + х₂ ≤ 400

3x₁ + 4x₂ ≤ 900

х₁ + Зх₂ ≤ 600

x₁ ≥ 0, х₂ ≥ 0

f = 60x₁ + 40x₂ Ì max

 

Войдя в MS EXCEL, создадим форму для ввода условий задачи. Для сформулированной задачи форма будет иметь вид:

	A	B	C	D	E	F	G
		Переменные
	Имя	пер. 1	пер.2
	Значение
	Ниж. гр.
	Верх. гр.
	Коэф. Ф.Ц				Макс.
		Ограничения
	Вид			Лев. час.	Знак	Прав. час.
	Огр. 1
	Огр. 2
	Огр. 3

 

Введенный текст является комментарием и на решение задачи не влияет. Введем исходные данные:

 

60 в В6; 40 в С6;

2 в В9; 1 в С9; 400 в F9;

3 в В10; 4 в С10; 900 в F10;

1 в В11; З в С11; 600 в F11.

Знак ≤ в Е9; Е10; Е11.

В результате получим:

 

	A	B	C	D	E	F	G
		Переменные
	Имя	пер. 1	пер.2
	Значение
	Ниж. гр.
	Верх. гр.
	Коэф. Ф.Ц				Макс.
		Ограничения
	Вид			Лев. час.	Знак	Прав. час.
	Огр. 1				≤
	Огр. 2				≤
	Огр. 3				≤

 

Введем зависимость для целевой функции. Установим курсор в D6. Курсор на кнопку Мастер функций. Один щелчок по левой кнопке мыши (M1). На экране появится диалоговое окно Мастер функций. Курсор в окно Категория на категорию Математические М1. Курсор в окно на СУММПРОИЗВ. М1.

На экране появится диалоговое окно СУММПРОИЗВ

В массиве 1 следует ввести В3: С3 (во все диалоговые окна адреса ячеек удобно вводить не с клавиатуры, а протаскивая мышь по ячейкам, чьи адреса следует ввести). В массив 2 введем В6:С6. Курсор в Готово М 1.

На экране в D6 прочитаем введенное значение целевой функции (=СУММПРОИЗВ (В3: СЗ; В6: С6)).

Введем зависимости для левых частей ограничений: курсор в D6; копиро­вать в буфер, курсор в D9; вставка из буфера. На экране в D9 будет введена функция (=СУММПРОИЗВ (ВЗ:СЗ; В9:С9)). Затем копируем D9 в D10 и в D11. На этом ввод данных закончен.

Теперь приступаем к поиску решения. Для этого используем функцию Сервис, Поиск решения …. На экране появится окно Поиск решения.

Назначим целевую функцию: курсор в окно Установить целевую ячейку; ввести адрес D6; ввести направление целевой функции - максимальное значе­ние.

Для ввода адресов искомых переменных: курсор в поле Изменяя ячейки; ввести адреса ВЗ: СЗ; курсор на функцию Добавить …; M1.

На экране появится диалоговое окно Добавить ограничения.

Введем граничные условия на переменные (пер.1 ≥ 0, пер.2 ≥ 0); ВЗ ≥ В4; СЗ ≥ С4 (в окне ссылка на ячейку ввести ВЗ: курсор на стрелку; М1; курсор на знак ≥; M1; курсор в правое окно; ввести В4; Добавить …. Аналогично вводится граничное условие СЗ ≥ С4; D9 ≥ F9; D10 ≥ F10; D11 ≥ F11. После 2 ввода последнего ограничения вместо Добавить … вводим ОК. На экране появится диалоговое окно Поиск решения с введенными условиями.

Если при вводе задачи возникает необходимость в изменении или удале­нии внесенных ограничений или граничных условий, то это делается с помо­щью команд Изменить …, Удалить ….

С помощью команд, находящихся в окне Параметры поиска решения, мож­но вводить условия для решения задач оптимизации всех классов. Команды, используемые по умолчанию, подходят для решения большинства практиче­ских задач. (В поле Максимальное время можно ввести время, не превышаю­щее 32767 с. (более 9 часов). В поле Предельное число итераций 100 подходит для решения большинства задач. Установление флажка Линейные модели обеспечивает применение симплекс-метода.) ОК. На экране появится диалого­вое окно Поиск решения.

Устанавливаем курсор на Выполнить. M1. После выполнения на экране появится диалоговое окно Результаты поиска решения. Решение найдено и результат оптимального решения задачи приводится в таблице, после в Типе отчета опции Результаты. ОК. По умолчанию найденное решение сохраняется.

 

	A	B	C	D	E	F	G
		Переменные
	Имя	пер. 1	пер.2
	Значение
	Ниж. гр.
	Верх. гр.
	Коэф. Ф.Ц				Макс.
		Ограничения
	Вид			Лев. час.	Знак	Прав. час.
	Огр. 1				≤
	Огр. 2				≤
	Огр. 3				≤

Из таблицы видно, что в оптимальном решении пер.1=140, пер.2=120. При этом максимальная выручка будет составлять D6=13200 ден. ед., а количество используемых ресурсов равно: pec.1=D9=400; pec.2=D10=900, pec.3=D11=500.

Если условия задачи будут несовместными, решение задачи не будет най­дено, о чем будет сообщено.

Анализ оптимального решения выполняется на основании применения по­ложений симплекс-метода, которые были изложены в пп. 3, 5, 6 и начинается после появления диалогового окна Результат поиска решения. С помощью этого диалогового окна можно вызвать отчеты трех типов: результаты, устойчивость, пределы.

Отчет по результатам начинается с установления курсора на результат ОК. На экране вызванный отчет на новом листе, на ярлычке которого указано название отчета M1. На экране высвечивается вызванный отчет.

Microsoft Excel 8.0 Отчет по резуль­татам

Целевая ячейка (Максимум)

Ячейка	Имя	Исходно	Результат
$D$6	Коэфф. ЦФ

 

 

Изменяемые ячейки

Ячейка	Имя	Исходно	Результат
$В$3	Значение пер. 1
$С$3	Значение пер. 2

 

 

Ограничения

Ячейка	Имя	Значение	Формула	Статус	Разница
$D$9	Огр.1		$D$9 ≤ $F$9	связанное
$D$10	Огр.2		$D$10≤$F$10	связанное
$D$11	Огр.3		$D$11≤$F$11	Не связан.
$B$3	Значение пер.1		$B$3 ≤ $B$4	Не связан.
$C$3	Значение пер.2		$C$3 ≤$C$4	Не связан.

 

Отчет состоит из трех таблиц:

В таблице 1 приводятся сведения о целевой функции. В столбце Исходно приводятся значения целевой функции до начала вычисления.

В таблице 2 приводится значение искомых переменных, полученных в ре­зультате решения задачи.

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

Для ограничений в графе Формула приводятся зависимости, которые были введены в диалоговое окно Поиск решения. В графе Значение приведены величины использованного ресурса. В графе Разница показано количество неиспользованного ресурса. Если ресурс использован полностью, то в графе Состояние указывается: Связанное; при неполном использовании ресурса в этой графе указывается: Не связанное. Для граничных условий приводятся аналогич­ные величины, с той лишь разницей, что вместо величины неиспользованного ресурса показана разность между значением переменной в найденном опти­мальном решении и заданным для нее граничным условием.

 

 

Microsoft Excel 8.0 Отчет по устой­чивости

 

Изменяемые ячейки

Ячей­ка	Имя	Результат и его значе­ние	Нормир. стои­мость	Целевой коэффи­циент	Допус­тимое увели­чение	Допус­тимое уменьшение
$В$3	Значение пер 1					--
$С$3	Значение пер 2					--

 

 

Ограничения

Ячей­ка	Имя	Результат и его значе­ние	Теневая цена	Ограничение правая часть	Допус­тимое увели­чение	Допус­тимое уменьшение
$D$9	Огр. 1
$D$10	Огр. 2
$D$11	Огр. 3				1Е+30

 

Отчет по устойчивости состоит из двух таблиц. В таблице 1 приводятся следующие значения для переменных:

w результат решения задачи;

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

w коэффициенты целевой функции;

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

В таблице 2 приводятся аналогичные значения для ограничений:

w величина использованных ресурсов;

w теневая цена, т. е. двойственные оценки, которые показывают, как из­менится целевая функция при изменении ресурсов на единицу;

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