Основы математического программирования (стр. 24 )

xij>0

достигается в клетках (2, 1) и (3, 3). Перечеркнем клетки (1, 2), (4, 2), , в которых время доставки не меньше 5.

bj ai	20	30	40	60
20	10	6	20 3	2
30	20 5	8	7	10 4
50	2	30 4	20 5	12
50	15	5	9	50 4

9. С помощью оставшихся не вычеркнутых клеток разгрузить клетки (2, 1) и (3, 3) не удается, поэтому Х4 является опорным решением.

Ответ:

min (Х) = 5 при Х =

2 0

7. Применение транспортной задачи для решения экономических задач

Задача о размещении производства с учетом транспортных затрат.

Имеется (проектируется) m пунктов производства с объемами производства а1, а2, …, am и n пунктов потребления с объемами потребления b1, b2, …, bn.

Затраты на производство единицы продукции в каждом i-ом пункте производства известны и равны Сi’ i = 1, 2, …, m.

Стоимости перевозки единицы груза от каждого i-ого производителя каждому j-ому потребителю известны и равны Cij’’ i = 1, 2, …, m. j = 1, 2, …, n.

Суммарные объемы производства превосходят суммарные объемы потребления.

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

Задача решается как транспортная задача, матрица стоимостей которой составляется как сумма матриц.

С = (Сij) = (Сi’ + Cij’’) i = 1, 2, …, m. j = 1, 2, …, n.

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

Задача о назначении, или проблема выбора.

Имеется m групп людей (станков) численностью a1, a2, …, am, которые должны выполнять n видов работ (операций) объемом b1, b2, …, bn.

Известна производительность каждой i-ой группы людей (станков) при выполнении j-ого вида работ (операций) Сij i = 1, 2, …, m. j = 1, 2, …, n.

Требуется так распределить людей (станки) для выполнения работ (операций), чтобы суммарный объем производства работ (операций) был максимальный.

Составим математическую модель задачи.

Обозначим Хij – число людей (станков) i-ой группы, занятых j-ым видом работ (операций)

m n

Z(X) = ∑ ∑CijXij max

i=1 j=1

n

∑ Xij = ai i = 1, 2, …, m

j=1

m

∑ Xij = bj j = 1, 2, …, n.

i=1

Xij ≥ 0 i = 1, 2, …, m. j = 1, 2, …, n.

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

m n

Z(X) = - ∑ ∑CijXij min

i=1 j=1

Можно также изменить критерий оптимальности.

Например, вместо Dij ≤ 0 "(i, j) использовать Dij ≥ 0 "(i, j)

8. Динамическое программирование: понятие, принципы

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

Процессы принятия решений, которые строятся по такому принципу, называются многошаговыми процессами.

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

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

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

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

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

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

Это значительно ускоряет процесс вычислений.

Однако, такое преимущество достигается лишь при двух условиях:

1. Критерий оптимальности должен быть аддитивен, т. е. общее оптимальное решение является суммой оптимальных решений для каждого шага.

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

Эти условия вытекают из принципа оптимальности Беллмана, лежащего в основе динамического программирования (1950 г.)

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

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

На каждом шаге производится сравнение вариантов будущего развития и заблаговременное отсеивание заведомо бесперспективных вариантов.

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

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

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

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

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

Общая постановка задачи динамического программирования.

Будем считать, что состояние x(k) рассматриваемой системы на k-ом шаге (k= 1, 2, …, n) определяется совокупностью чисел

x(k) = (x1(k), x2(k), …, xm(k)),

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

Необходимые условия:

1. Условие отсутствия последействия.

Состояние x(k), в которое перешла система S, зависит от исходного состояния х(k-1) и выбранного управления mk и не зависит от того, каким образом система S перешла в состояние х(k-1).

2. Условие аддитивности. Если в результате реализации k-ого шага обеспечен определенный доход Gk(x(k-1), mk), также зависящий от исходного состояния x(k-1) и выбранного управления mk, то общий доход за n шагов составит

n

G(m) =∑ Gk(x(k-1), mk),

k=1

где m = (m1, m2, …,mn)

Задача состоит в нахождении оптимальной стратегии управления, т. е. такой совокупности управлений m* = (m*1, m*2, …,m*n), в результате реализации которых система S за n шагов переходит из начального состояния Ss = x(0) в конечное Sf = x(n) и при этом функция дохода G(m) принимает наибольшее значение.

Принцип оптимальности Беллмана.

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

Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-ом шаге, затем на двух последних шагах, затем на трех последних и т. д., вплоть до первого шага.

Таким образом, решение задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, n-м шаге.

Для того, чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление mok , обеспечивающее максимальное значение функции Gn(x(n-1), mn).

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

Другими словами.

На всех шагах, кроме последнего должны учитываться последствия принимаемого решения. На последнем шаге принятое решение должно давать максимальный эффект.

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