02_Сущность методов

C_ij-(U_i+V_j)=0 для x_ij≥0 (1)

(для занятых клеток) и

ΔC=C_ij-(U_i+V_j)≥0, (;) (2)

(для свободных клеток)³.

Поскольку число неизвестных потенциалов (m+n) всегда на единицу больше числа уравнений (числа заполненных клеток) N=m+n-1, то выбираем строку, где есть занятая клетка и для этой строки назначаем потенциал равным нулю и легко находим последовательно из уравнений (1) значения остальных потенциалов.

Если же число заполненных клеток N<m+n-1, то вводим дополнительно необходимое количество занятых клеток с нулевыми перевозками х_ij=0, которые нужны для определения потенциалов из уравнений (1).

Затем для всех свободных клеток из соотношений (2) определяем величину ΔC_ij и, если все ΔC_ij>0, то получим оптимальный план перевозок, если же встречаем отрицательные ΔC_ij, то план не оптимален и его надо улучшать.

Улучшение плана перевозок

Среди пустых клеток с отрицательными значениями ΔC_ij выбираем ту, у которой ΔC_ij наименьшая. Эта пустая клетка рекомендуется к заполнению, в результате которого одна из заполненных клеток станет пустой т.е. х_ij из не основных (нулевых) переходит в основные (положительные). Остается определить, какая из основных переменных должна стать не основной.

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

Наиболее часто контур имеет вид прямоугольника, но возможны фигуры другого типа (рис.1).

Рис.1

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

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

Открытая модель транспортной задачи

Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности ∑a_i>∑b_j;.

б) суммарные потребности превышают суммарные запасы ∑a_i<∑b_j.

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

В случае (а) вводится фиктивный потребитель B_n+1 потребности которого b_n+1=∑a_i-∑b_j

В случае (б) вводится фиктивный поставщик A_m+1 запасы которого a_m+1 =∑b_j-∑a_i

Стоимости перевозок в обоих случаях полагаются равными нулю.

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

П Р А К Т И К А № 6

Пример решения расчетной работы: шифр – 123456

n	=	5	m	=	4
u1 (тыс.м3)	=	35	v1 (тыс.м3)	=	25
u2 (тыс.м3)	=	45	v2 (тыс.м3)	=	35
u3 (тыс.м3)	=	55	v3 (тыс.м3)	=	45
u4 (тыс.м3)	=	65	v4 (тыс.м3)	=	55
u5 (тыс.м3)	=	45	v5 (тыс.м3)	=	65

Баланс земляных масс:

∑V_Выемок = 35+45+55+65+45=245 тыс.м³

∑V_{Насыпей} = 25+35+45+55=160 тыс.м³

Требуется разработка грунтового карьера мощностью 245-160=85 тыс.м³. Транспортная задача носит открытый характер.

Т.к. m<n, то схема продольного профиля примет вид:

кар-р	u1	v1	u2	v2	u3	v3	u4	v4	u5
85	35	25	45	35	55	45	65	55	45

Составляем матрицу планирования и исходное опорное решение.

Табл. 1

	u1	-0,5	u2	0,5	u3	1,5	u4	2,5	u5	2,5
v1		0,5		0,5	7	1,5		2,5		3,5
0	ΔС=	1,0	ΔС=	0	25	0	ΔС=	0	ΔС=	1,0	25
v2		1,5		0,5	6	0,5	5	1,5		2,5
-1,0	ΔС=	3,0	ΔС=	1,0	25	0	10	0	ΔС=	1,0	35
v3		2,5		1,5		0,5	4	0,5		1,5
-2,0	ΔС=	5,0	ΔС=	3,0	ΔС=	1,0	45	0	ΔС=	1,0	45
v4		3,5		2,5		1,5	3	0,5	2	0,5
-2,0	ΔС=	6,0	ΔС=	4,0	ΔС=	2,0	10	0	45	0	55
vкар-ер	1	0,25	9	1,25	8	2,25		3,25		4,25
0,75	35	0	45	0	5	0	ΔС=	0	ΔС=	1,0	85
	35		45		55		65		45

Всего должно быть заполненных клеток N=n+m=5+5-1=9, заполнено-9.

Проверки правильности построения по горизонтали и вертикали:

∑=25=25

∑=25+10=35

∑=45=45

∑=10+45=55

∑=35+45+5=85

∑=35=35

∑=45=45

∑=25+25+5=55

∑=10+45+10=65

∑=45=45 - сходятся.

Определение потенциалов на первом этапе (см. табл.1)

Назначим V₁=0, тогда для остальных клеток:

• для занятых клеток C_ij-(U_i+V_j)=0

• для свободных ΔС=C_ij-(U_i+V_j), если ΔС<0, то план не оптимальный

Т.к. ΔС<0, отсутствуют, то план можно считать оптимальным и , следовательно, можно определить транспортные расходы.

5. Транспортные расходы:

Z_min=0,25*35+1,25*45+1,5*25+0,5*25+2,25*5+1,5*10+0,5*45+0,5*10+0,5*45==191,25 тыс.руб

5. В случае если исходный план не оптимален, например:

	u1	-0,5	u2	0,5	u3	1,5	u4	1,5	u5	1,5
v1		0,5		0,5		1,5		2,5		3,5
0	ΔС=	1,0	ΔС=	0	25	0	ΔС=	1,0	ΔС=	2,0	25
v2		1,5		0,5		0,5		1,5		2,5
0	ΔС=	2,0	ΔС=	0	ΔС=	-1,0	35	0	ΔС=	1,0	35
v3		2,5		1,5		0,5		0,5		1,5
-1,0	ΔС=	4,0	ΔС=	2,0	25	0	20	0	ΔС=	1,0	45
v4		3,5		2,5		1,5		0,5		0,5
-1,0	ΔС=	5,0	ΔС=	3,0	ΔС=	1,0	10	0	45	0	55
vкар-ер		0,25		1,25		2,25		3,25		4,25
0,75	35	0	45	0	5	0	ΔС=	1,0	ΔС=	2,0	85
	35		45		55		65		45

т.е. присутствуют ΔС<0 необходимо оптимизировать исходное решение, для этого выбираем контур одной из вершин которого является клетка с наименьшей величиной ΔС.

+о	─	-35			25	─	10
│		│			│		│
-25	─	+20			о	─	45

Среди отрицательных вершин выбираем наименьшее значение 25 и прибавляем его к положительным вершинам и отнимаем от отрицательных вершин. Получим новый контур перевозок с одной свободной вершиной и не нарушенным балансом перевозок.

Далее строим новый план перевозок. Не трудно убедиться, что это есть таблица 1. Определяем минимальные транспортные расходы.

Лекция №7 Динамическое программирование

Постановка задачи

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

В общем случае задача динамического программирования формулируется следующим образом. Пусть данная физическая система S находится в некотором начальном состоянии S₀ и является управляемой. Благодаря осуществлению некоторого управления uU указанная система переходит из начального состояния S₀ в конечное состояние S_кон. При этом качество каждого из реализуемых управлений uU характеризуется соответствующим значением функции W(u). Задача состоит в том, чтобы из множества возможных управлений uU найти такое u*U, при котором функция W(u) принимает экстремальное значение W(u*).

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

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

Таблица 1

	Время t, в течение которого эксплуатируется дорога, лет
	0	1	2	3	4	5
Эффективность перевозок R(t) в стоимостном выражении, тыс.руб.	80	75	65	60	60	55
Ежегодные затраты Z(t), связанные с содержанием и ремонтом дороги, тыс. руб.	20	25	30	35	45	55

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

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

Общая эффективность перевозок за пятилетку составляется из ежегодной, т.е. если u₁, u₂, ..., u₅ - управления, применяемые в начале каждого сезона, W(τ_i;u_i) - эффективность перевозок за i-й год пятилетки, то

,

где u=(u₁, u₂, u₃, u₄, u₅), τ_i - возраст покрытия в начале i-го сезона,

⁵

Алгоритм решения задач методом динамического программирования. Принцип оптимальности Беллмана.

Введем некоторые обозначения и сделаем необходимые для дальнейшего предположения:

1. Состояние рассматриваемой системы S на k-ом шаге () определяется совокупностью чисел x^(k)=(), которые получены в результате реализации управления u_k, обеспечивающего переход системы S из состояния x^(k-1) в состояние x^(k).

2. Состояние x^(k), в которое перешла система S, зависит от данного состояния x^(k-1) и выбранного управления U_k и не зависит от того, каким образом система S перешла в состояние x^(k-1). Далее будем считать, что если в результате реализации k-гo шага обеспечен определенный доход, также зависящий от исходного состояния системы x^(k-1) и выбранного управления U_k, равный W_k(x^(k-1);u_k), то общий доход за n шагов составляет