Экономический смысл элементов таблицы.

Пример: p₂ = -2 – 2-й поставщик получает 2 денежные единицы за доставку 90 единиц продукции. q₂ = 2 - 2 денежные единицы платит второй потребитель за доставку ему 156 единиц продукции.

IX. РЕШЕНИЕ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ КАПВЛОЖЕНИЙ МЕТОДОМ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

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

Рассмотрим нелинейную задачу распределения ресурсов между предприятиями отрасли. Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через f_j(x_j) прирост мощности или прибыли на j-том предприятии, если оно получит x_j рублей капвложений. Требуется найти такое распределение (х₁, х₂,..., х_n) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

Z=f₁(x₁)+f₂(x₂)+...+f_n(x_n)

при ограничении по общей сумме капвложений

х₁ + х₂ +...+х_n = b

причём будем считать, что все переменные x_j принимают только целые значения x_j =1,2,...

Функции f_j(x_j) мы считаем заданными, заметив, что их определение -довольно трудоёмкая экономическая задача.

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

Введём параметр состояния и определим функцию состояния. За параметр состояния x примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k(x) определим как максимальную прибыль на первых k предприятиях, если они вместе получат x рублей. Параметр x может меняться от 0 до b. Если из x рублей k-ое предприятие получит Х_к рублей, то каково бы ни было это значение, остальные x-Х_к рублей естественно распределить между предприятиями от 10-го до (к-1)-го предприятия, чтобы была получен максимальная прибыль F_k-1(x-x_k). Тогда прибыль k предприятий будет равна f_k(x_k) + F_k-1(x-x_k). Надо выбрать такое значение x_k между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению:

F_k(x) = max {f_k(x_k) + F_k-1(x-x_k)}

0 £ X £ x

для k=2,3,....,n.Если же k=1,то

F₁(x)=f₁(x).

Рассмотрим конкретный пример. Пусть производственное объединение состоит из 4-х предприятий (k=4).Общая сумма капвложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей.

Значения функций f_j(x_j) приведены в табл. 1.

Прежде всего заполняем табл.3. Значения f₂(x₂) складываем со значениями F₁(x-x₂)=f₁(x-x₂) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой. Заполняем табл.3.

Продолжая процесс табулируем функции F₃(x), x₃(x) и т.д. В табл.6 заполняем только одну диагональ для значения x=700.

 

 

Таблица 1.

Xj
f1(xj)
f2(xj)
f3(xj)
f4(xj)

 

Таблица 2.

	x-х2
х2
									---
								---	---
							---	---	---
						---	---	---	---
					---	---	---	---	---
				---	---	---	---	---	---
			---	---	---	---	---	---	---

 

Таблица 3.

x
F2(x)
x2(x)
x2(x)

 

Таблица 4.

	x-x3
x3
		0*	15*	26*	38*
					49*	59*		74*	---
						67*	74*	---	---
						74*	---	---	---
						---	---	---	---
					---	---	---	---	---
				---	---	---	---	---	---
			---	---	---	---	---	---	---

 

 

Таблица 5.

x
F3(x)
x3(x)
x3(x)
x3(x)

 

 

Таблица 6.

	x-x4
x4
							93*

 

 

Наибольшее число диагонали в табл.6:

Z_max = 93 тыс. рублей

X4* = X(700) = 200

X3*+X2*+X1*=700–200=500

 

В табл.5:

где сумма равна 500

Х3* = 100

Х1*+Х2*=500-100=400

 

В табл.3.

где сумма равна 400

Х2*=100

Х1*=400-100=300

 

Оптимальная программа: 1) Х1*=300; Х2*=100;

Х3*=100; Х4*=200

Z_max(X1*;... X4*)=38+10+11+34=93 так как выполнилось равенство

Z_max(X1*;... X4*) = 101 эта программа оптимальна

Ответ: Оптимальная производственная программа имеет вид:

Х1* = 300; Х2* = 100; Х3* = 100; Х4* = 200, при этом максимальная прибыль составляет 93 тыс. руб.

 

X. РЕШЕНИЕ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК.

 

Трехкритериальная задача:

{

z₁ = c₁₁x₁ + c₁₂x₂ ® max

z₂ = c₂₁x₁ + c₂₂x₂ ® max

z₂ = c₃₁x₁ + c₃₂x₂ ® max

{

где критерии ранжированы и пронумерованы по важности и на переменные наложены ограничения:

а₁₁x₁ + a₁₂x₂ £ b₁

a₂₁x₁ + a₂₂x₂ £ b₂

a₃₁x₁ + a₃₂x₂ £ b₃

x₁ ³ 0,x₂ ³ 0

 

Исходные данные задачи имеют вид:

 

		Δ1
		Δ2
		--
-6	-7	-87

 

{

Подставляя данные индивидуального задания получим:

z₁ = 1x₁ + 7x₂ ® max

z₂ = 4x₁ + 4x₂ ® max

z₂ = 8x₁ + 2x₂ ® max

	{

x₁ + 4x₂ £ 40

5х₁ + 3x₂ £ 64

-6x₁ - 7x₂ £ -87

x₁ ³ 0, x₂ ³ 0

	{

x₁ + 4x₂ £ 40 (1)

5х₁ + 3x₂ £ 64 (2)

6x₁ + 7x₂ ³ 87 (3)

x₁ ³ 0, x₂ ³ 0

 

{

Максимизируем z₁ при условиях (1) - (3) и графически решаем. Решение -точка А, найдём её координаты:

х₁ = 0 х₁* = 0

6х₁ + 7х₂ = 87 х₂* =20

 

Z₁*_max = 140

Пусть Δ₁ = 56, тогда Z₁* - Δ₁ = 84 и вводим новое ограничение

х₁ + 7х₂ ³ 84 (4)

Максимизируем Z₂ при условиях (1)-(3) и (4). Решение - точка В.

{

Найдём её координаты

х₁ + 4х₂ = 80 х₁* = 0,97

5x₁ + 3х₂ = 64 х₂* = 19,76

 

Z₂*_max = 4*0,97 + 4*19,76 = 82,87

 

Пусть Δ₂ = 18.87, тогда Z₂* - Δ₂ = 82,88-18,87 = 64 и вводим новое ограничение

4х₁ + 4х₂ ³ 64 (5)

Максимизируем z₃ при условиях (1)-(3) и (5). Решение - точка С. Её координаты х₁* = 6,09; х₂* = 11,13

Получаем оптимальное решение трёхкритериальной задачи при х₁ = 6,09 и х₂ = 11,13.

Z_{1 max} = 1*6,09 + 7*11,13 = 84

Z_{2 max} = 4*6,09 + 4*11,13 = 68,88

Z_{3 max} = 8*6,09 + 2*11,13 = 70,98