Двойственность в линейном программировании. Анализ оптимального плана по двойственным оценкам основных переменных

Рис. 4.1.5

1-я таблица – целевая  ячейка – дает значение целевой  функции, которая уже имеется  в таблице EXCEL, значит, эти данные  избыточны. 

2-я таблица – изменяемые  ячейки – дает значение переменных, которые уже имеются в таблице  EXCEL, эти данные тоже избыточны. 

3-я таблица – ограничения  – дает оценку ограничений.  Колонка «значение» дает значения  планового расхода ресурсов и  переменных – эти данные имеются  в таблице EXCEL и здесь избыточны.  Столбец «статус» значением «связанное»  отмечает ограничения (не больше  или не меньше), которые в результате  решения превратились в строгие  равенства, прочие ограничения  имеют статус «несвязанные». Столбец  «разница» показывает, на какую  величину ограничения отклонились  от строгого равенства. Так,  например, ограничение 1-го ресурса  500, плановое значение 271,6, разница  = 500 – 271,6 = 228,4.

 Отчет по устойчивости  изображен на рис. 4.1.6. Он состоит  из двух таблиц.

 Отчет по устойчивости 

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

Ячейка Имя Результат  Норир.  Значение градиент

$B$8 Перем Пр1 86 0

$C$8 Перем Пр2 0 -22,8

$D$8 Перем Пр3 268 0

 

Ограничения

Ячейка Имя Результат. Лагранжа  значение Множитель

$G$2 Рес 1 Расход 271,6 0

$G$3 Рес 2 Расход 310 20

$G$4 Рес 3 Расход 2200 4,4

Рис. 4.1.6

       Таблица «изменяемые ячейки» показывает значения переменных, которые уже имеются в таблице EXCEL. Столбец «нормируемый градиент» показывает, как влияет увеличение переменных на единицу на величину целевой функции. Таблица «ограничения» содержит важную информацию в столбце «Лагранжа множители». Эти величины в литературе имеют различные названия: объективно обусловленные оценки (О.О.О.) по Л. Канторовичу, двойственные оценки по Д. Данцигу, оптимальные цены, теневые цены и другие. В дальнейшем будем называть их наиболее распространенным именем – двойственные оценки и обозначать – vi, где i – номер ограничения. В данном примере v1 = 0, v2 = 20,0, v3 = 4,4. Отчет по пределам показан на рис. 4.1.7.

Отчет по пределам

Ячейка Целевое Значение  имя
$G$6 Цены ЦФ 15880
Ячейка Изменяемое Значение имя	Нижний Целевой   предел результат	Нижний Целевой   предел результат
$B$8 Перем Пр1 86	0 10720	86 15880
$C$8 Перем Пр2 0	0 15880	0 15880
$D$8 Перем Пр3 268	0 5160	268 15880

Рис. 4.1.7.

      В этом отчете уже в третий раз дается значение целевой функции 15880, в пятый раз значение переменных (х1 = 86, х2 = 0, х3 = 268). Нижний предел для всех переменных = 0, так, установлены ограничения по переменным. Верхний предел равен соответственно 86, 0 и 268, так устанавливают ограничения по ресурсам. Целевой результат показывает значение целевой функции при соответствующих значениях переменных. Если х1 = 0, то ЦФ = 10720 и т.д.

 Запишем математическую  модель рассмотренной задачи  в общем виде:

Пусть:

В-бюджет, т.е. количество денег, которое можно израсходовать  на приобретение ресурсов для производства продукции, а si – рыночная цена i-го ресурса. Тогда единственное ограничение по ресурсам будет выглядеть следующим образом:

Смысл этого ограничения - нельзя израсходовать ресурсов на сумму больше, чем В.

 Здесь:  aijxj - расход i-го ресурса в натуральном выражении по j-му технологическому способу;

- расход i-го ресурса в натуральном выражении по всем способам;

- суммарная цена i-го ресурса, израсходованного по всем способам;

  - суммарная цена всех ресурсов по всем технологическим способам.

Решим задачу на максимум продукции  с ограничением по бюджету. За основу возьмем электронную модель на рис. 4.1.3. и дополним ценами ресурсов si и бюджетом В (рис. 4.1.8)

Рис. 4.1.8

 Дополнительные величины:

 H2:H4 – цены ресурсов (задаются);

 I2:I4 – издержки (вычисляются);

 I2 = G2*H2;

 I3:I4 – копируется из I2;

 H6 = 5000 – бюджет (задается);

 I6 – издержки всего (вычисляются);

 I6 = СУММ (I2:I4).

 Ограничения:

B8:D8 ≥ 0 – неотрицательности переменных;

 I6≤ H6 – совокупные издержки не больше бюджета.

 Будет получено решение 

x1 = 0; x2 = 0; x3 = 409,84.

v = 3,08 – двойственная оценка ограничения по бюджету – увеличение бюджета на единицу увеличивает валовой продукт на 3,28.

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

 

 

 

 

 

 

 

 

3 Анализ оптимального  плана по двойственным оценкам  основных переменных.

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

1. изменение запасов ресурсов;
2. внедрение нового технологического способа производства, позволяющего снизить расход сырья А и В;
3. произошедшие изменения в ценовой политике на предприятии;
4. предполагается выпуск нового вида продукции.

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

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

1. Двойственные оценки характеризуют дефицитность ресурсов. Величина ui в оптимальном решении двойственной задачи является оценкой i-го ресурса; чем больше значение оценки ui , тем выше дефицитность ресурса. Для недефицитного ресурса ui=0.
2. Двойственные оценки показывают, как влияют изменения правой части ограничений (запасов ресурсов) на значение целевой функции. Практический интерес представляет границы (нижняя и верхняя) изменения ресурсов, в которых величины оценок остаются неизменными.
3. Двойственные оценки являются показателем эффективности производства отдельных видов продукции с позиции критерия оптимальности. С этой точки зрения в оптимальный план может быть включена лишь та продукция j-го вида, для которой выполняется условие

 

Где - оптимальное значение двойственной оценки i-го ресурса;

         - технологические коэффициенты;

          - доход, получаемый  с единицы продукции j-го вида;

        m – количество видов ресурсов.

4. Двойственные оценки позволяют провести сравнение суммарных условных затрат и результатов.

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

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

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

1.  Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.

2.  Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.

3.  Математическое моделирование  в задачах. Белолипецкий В.М., Шокин Ю.И.

4.  Математическое Белолипецкий В.М.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Контрольная задача 1

Оптимизация производственной программы промышленного предприятия.

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

      Ресурсы оборудования, сырья, труда ограничены (см. табл. 3).

      Выпуск продукции А, Б и В не может быть меньше заключенных на эту продукцию договоров (см.  табл. 2).

В таблице 1 приведены нормативы  затрат ресурсов на производство продукции  и прибыль при использовании  различных технологических способов  в расчёте на единицу продукции.

Таблица 1

Наименование ресурсов	Ед.изм.	Продукция А		Продукция Б		Продукция В
		технологич. способы		технологич. способы		техн. способы
		1	2	1	2	1	2	3
Оборудование:	станко-час.
новое		10	-	20	-	30	32	-
старое		-	12	-	25	-	-	40
Сырье:	т
высококачественное		2	-	5	-	10	10	-
стандартное		-	2	-	5	-	-	9
Труд:	чел.-час.
высококвалифицированный		18	-	30	-	40	-	-
средней квалификации		-	20	-	32		48	50
Прибыль	т.руб.	300	500	350	700	720	1200	1300

 

Таблица 2

		Объемы заключенных договоров
Номер варианта	Продукция
	А	Б	В
6	5000	2250	4000

 

Таблица 3

		Объемы ресурсов
Номер варианта	Оборудование, станко-час.		Сырье, т		Труд, чел.-час.
	новое	старое	высококач.	стандарт.	высококвалиф.	ср. квалиф.
6	160600	400600	70600	40600	220000	160000

 

Разработка модели ЛП.

Переменные задачи.

x₁ - выпуск продукции А первым технологическим способом;

x₂ - выпуск продукции А вторым технологическим способом;

x₃ - выпуск продукции Б первым технологическим способом;

x₄ - выпуск продукции Б вторым технологическим способом;

x₅ - выпуск продукции В первым технологическим способом;

x₆ - выпуск продукции В вторым технологическим способом;

x₇ - выпуск продукции В третьим технологическим способом.

 

1. Блок ограничений по использованию ресурсов.

1. Оборудование новое, станкочасы.

10 x₁+20x₃+30x₅+32x₆≤160600

2. Оборудование старое, станкочасы.

12x₂+25x₄+40x₇≤400600

3. Сырьё высококачественное, тонн.

2x₁+5x₃+10x₅+10x₆≤70600

4. Сырьё стандартное, тонн.