Определение ценности дополнительной единицы дефицитного ресурса

Результаты анализа сведем в таблицу:

 

Ограничение	Тип ресурса	Максимальное изменение запаса ресурса	Максимальное изменение ЦФ
Ограничение по времени работы дубильного участка	Дефицитный	47-45=2 ч	ден.ед.
Ограничение по времени работы раскройного участка	Дефицитный	125-65=60 ч
ограничение по времени работы завершающего участка	Недефицитный	165-150=15 ч

Ценность дополнительной единицы ресурса (теневая цена):

Ценность каждого дополнительного часа работы дубильного участка:

-

Т.е. каждый дополнительный час работы дубильного участка принесет дополнительную прибыль 1, 5 ден. ед.

Ценность каждого дополнительного часа работы раскройного участка:

-

Т.е. каждый дополнительный час работы раскройного участка принесет дополнительную прибыль 0, 5 ден. ед.

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

5.3.5 Анализ изменения коэффициентов целевой функции

Обозначим через и доходы от продажи одной единицы изделия B и одной единицы изделия Г соответственно. Тогда:

.

Напомним, что угловым коэффициентом прямой является коэффициент при в уравнении прямой с угловым коэффициентом (это уравнение, в котором выражена переменная y), т.е.

= .

Угловой коэффициент равен тангенсу угла наклона данной прямой к положительному направлению оси OX.

Если выразить переменную , то коэффициент при есть тангенс угла наклона прямой к положительному направлению оси OY.

=

Целевая функция имеет вид

Если (линия уровня С), то уравнение

-

задает семейство параллельных прямых,

или

при

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

 

Переместим линию уровня в точку максимума D.

При уменьшении ее углового коэффициента прямая d совместится с граничной линией (2), а при увеличении ее углового коэффициента – с граничной линией (1).

Точка D будет оставаться оптимальной точкой до тех пор, пока угол наклона линии к оси OX будет лежать между углами наклона этих прямых, т.е.

и, значит,

 

Найдем , , , .

Для линии (1):

= - 1

=-1

Для линии (2)

= - 3

=

Поскольку , = - 3, = - 1, то

При условии, что прибыль от продажи единицы изделия остается на прежнем уровне , имеем:

,

т.е . при неизменной прибыли от изделия Г прибыль от изделия В может колебаться от 2 до 6 ден.ед., что не повлечет изменения оптимального решения.

Точка D будет оставаться оптимальной точкой и до тех пор, пока угол наклона линии к оси OY будет лежать между углами наклона этих прямых, т.е.

,

А поскольку =-1, = , = , то

.

При условии, что прибыль от продажи единицы изделия остается на прежнем уровне , имеем:

,

т.е . при неизменной прибыли от изделия В прибыль от изделия Г может колебаться от 1 до 3 ден.ед., что не повлечет изменения оптимального решения.

А что будет, если угловой коэффициент (наклон к оси OX) опорной прямой станет меньше углового коэффициента прямой (2)? В этом случае точкой максимума функции станет точка E (40; 0), т.е. производить изделия Г станет невыгодно, потребление первого ресурса (времени работы дубильного участка) сократится и он перестанет быть дефицитным. Дефицитным останется второй ресурс – время работы раскройного участка.

 

 

Если угловой коэффициент (наклон к оси OX) опорной прямой станет больше углового коэффициента прямой (1),

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

и 165 (3), т.е.

С(7; 33),

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

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

 

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

• в задаче (1) требуется минимизировать целевую функцию: , а в задаче (2) - максимизировать: ;
• все ограничения задачи (1) – неравенства вида , все ограничения задачи (2) – неравенства –вида ;
• в задаче (1) n неизвестных и m ограничений (без учета условий неотрицательности), в задаче (2) m неизвестных и n ограничений (без учета условий неотрицательности);
• матрицы из коэффициентов при переменных , , …, задач (1) и при переменных , , …, задачи (2) являются взаимно транспонированными;
• правые части системы ограничений задачи (1) – это коэффициенты целевой функции задачи (2); коэффициенты целевой функции задачи (1) – это правые части системы ограничений задачи (2);
• каждому ограничению задачи (1) в виде неравенства соответствует условие неотрицательности ассоциированной с этим ограничением переменной задачи; каждому ограничению задачи (1) в виде равенства соответствует переменная задачи (2) без ограничений на знак
• каждому ограничению задачи (2) в виде неравенства соответствует неотрицательная переменная задачи (1), каждому ограничению задачи (2) в виде равенства соответствует переменная задачи (1) произвольного знака.

 

Такие задачи называют парой двойственных задач линейного программирования (или просто двойственной парой ).

 

Задача 1	Задача 2

 

Пример 1. Построить задачу, двойственную следующей задаче линейного программирования:

Решение

Умножим первое ограничение – неравенство на -1. Задача примет вид задачи (2) симметричной пары двойственных задач:

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

.

Функция максимизируется, так как целевая функция исходной задачи минимизируется.

Умножаем коэффициенты при на соответствующие переменные двойственной задачи и складываем их:

.

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

.

Неравенство имеет вид « », потому что целевая функция двойственной задачи максимизируется. Аналогично составляются еще два ограничения двойственной задачи (соответствуют переменным , ):

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

Окончательно двойственная задача имеет вид:

Пример 2. Построить задачу, двойственную данной задаче линейного программирования:

Решение

Будем использовать условия, которым должны удовлетворять двойственные задачи. Умножим ограничения – неравенства на (-1), так как в задаче на максимум они должны иметь вид « ». Исходная задача запишется в виде:

Составим двойственную задачу:

Переменная , соответствующая ограничению равенства, может быть любого знака.

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

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

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

(1)

(2)

Иначе, если при подстановке оптимального решения в систему ограничений i-е ограничение исходной задачи выполняется как строгое неравенство, то i-я координата оптимального решения двойственнойзадачи равна нулю,

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

 

Задача 1	Задача 2
Подставим оптимальное решение в систему ограничений Пусть, например, , тогда Если, например, , то	Подставим оптимальное решение в систему ограничений Пусть, например, , тогда Если, например, , то

 

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

 

Решение

1. Составим двойственную задачу, запишем ограничения:

 

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

 

Уравнения границ области:

 

	-2

 

 

		-1

 

 

 

Область допустимых решений полученной задачи – многоугольник ABCDЕ.

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

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

Следовательно, оптимальное решение:

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

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

Учитывая это, из системы ограничений исходной задачи получим:

Оптимальное решение исходной задачи:

.

Ответ:

 

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

Решение

Составим задачу, двойственную к исходной, и запишем ограничения:

Решим полученную задачу симплекс – методом.

Сведем задачу на максимум к задаче на минимум. Для этого целевую функцию умножим на -1, получим

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

Базисные перемененные , свободные .

Выражаем базисные переменные через свободные:

Получим систему уравнений допустимого вида.

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

Таблица 1

Базисные переменные	Свободные члены							Отно- шение
W		5

 

 

В последней строке есть положительные коэффициенты. Возьмем коэффициент в столбце переменной . Разрешающим элементом является 3.

Строим таблицу 2.

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

Умножаем третью строку новой таблицы на ( -1) и складываем с первой, умножаем на ( -2) и складываем со второй, умножаем на ( -5) и складываем с четвертой строкой старой таблицы.

Таблица 2

Базисные переменные	Свободные члены							Отно- шение
			2/3	-1			-1/3
			1/3	-2			-2/3
			1/3				1/3
W	-15		1/3	-6			-5/3

 

В новой таблице последняя строка имеет положительный коэффициент в столбце переменной . Разрешающим элементом является 1/3.

Строим таблицу 3. Для этого умножаем выделенную стрелкой строку на и записываем результат вместо этой строки в таблицу 3.

Умножаем вторую строку новой таблицы на и складываем с первой, на и складываем с третьей и на и складываем с четвертой строкой предыдущей таблицы.

Таблица 3

Базисные переменные	Свободные члены
						-2
				-6			-2
						-1
W1	-16			-4		-1	-1

 

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

=2, =3, =1, =0, =0, =0,

,

.

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

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

Учитывая это и в силу теоремы 2, из системы ограничений исходной задачи получим систему:

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

Решив систему:

получим .

Оптимальное решение исходной задачи

Ответ:

4 Экономико-математическая модель межотраслевого баланса (модель Леонтьева).

Рассмотрим модель межотраслевого баланса, называемую еще моделью Леонтьева или моделью «затраты-выпуск».

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

Рассмотрим отрасль i, i = 1, 2, …, n. Она выпускает некую продукцию за данный промежуток времени (например, за год) в объеме x_i, который еще называют валовым выпуском. Часть объема продукции x_i, произведенная i-ой отраслью используется для собственного производства в объеме x_ii, часть – поступает в остальные отрасли j = 1, 2, …, n для потребления при производстве в объемах x_ij, и некоторая часть объемом y_i – для потребления в непроизводственной сфере, так называемый объем конечного потребления. Перечисленные сферы распределения валового продукта i-ой отрасли приводят к соотношению баланса

, i = 1, 2, …, n.

Введем коэффициенты прямых затрат a_ij, которые показывают, сколько единиц продукции i-ой отрасли затрачивается на производство одной единицы продукции в отрасли j. Тогда можно записать, что количество продукции, произведенной в отрасли i в объеме x_ij и поступающей для производственных нужд в отрасль j, равно

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

, i = 1, 2, …, n. (1)

Введя вектор валового выпуска X, матрицу прямых затрат A и вектор конечного потребления Y

модель Леонтьева (1) можно записать в матричном виде

X = AX + Y (2)

Матрица A ≥ 0, у которой все элементы a_ij ≥ 0 (неотрицательны), называется продуктивной матрицей, если существует такой неотрицательный вектор X ≥ 0, для которого выполняется неравенство

X > AX.

Это неравенство означает, что существует хотя бы один режим работы отраслей данной экономической системы, при котором продукции выпускается больше, чем затрачивается на ее производство. Другими словами, при этом режиме создается конечный (прибавочный) продукт Y = X – AX > 0.

Модель Леонтьева с продуктивной матрицей A называется продуктивной моделью.

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

Для проверки продуктивности матрицы A также достаточно существования обратной матрицы B = (E – A)^-1 с неотрицательными элементами, где матрица E – единичная матрица

.

С помощью модели Леонтьева (2) можно выполнить три вида плановых расчетов, при условии соблюдения условия продуктивности матрицы A:

1) Зная (или задавая) объемы валовой продукции всех отраслей X можно определить объемы конечной продукции всех отраслей Y

Y = (E – A)X

2) Задавая величины конечной продукции всех отраслей Y можно определить величины валовой продукции каждой отрасли

X = (E – A)^-1Y (3)

3) Задавая для ряда отраслей величины валовой продукции, а для всех остальных отраслей – объемы конечной продукции, можно найти величины конечной продукции первых отраслей и объемы валовой продукции вторых.

Матрица

B = (E – A)^-1

называется матрицей полных материальных затрат. Ее смысл следует из матричного равенства (3), которое можно записать в виде X = BY. Элементы матрицы B показывают, сколько всего необходимо произвести продукции в i-ой отрасли, для выпуска в сферу конечного потребления единицы продукции отрасли j.

⇐ Предыдущая12345678Следующая ⇒

Поделиться: