Задание 2. Планирование перевозок

Товары с m баз поставляются в п магазинов. Потребности магазинов в товарах равны,. Запасы товаров на базах составляют,. Затраты на перевозку 1 тыс.ед. товара в ден.ед. представлены матрицей затрат. Запланировать перевозку с минимальными затаратами при данном дополнительном условии.

Требуется:

1) Свести исходные данные в таблицу:

• 2) Составить математическую модель задачи;
• 3) Привести ее к стандартной транспортной задаче (с балансом);
• 4) Построить начальный опорный план задачи (методом минимального элемента);
• 5) Решить задачу (методом потенциалов);
• 6) Проанализировать результаты решения.

, .

Необходимо полностью освободить 3-ю базу.

Решение:

1) Сведем исходные данные в таблицу:

2) Построим математическую модель задачи. Пусть (,) — количество товара, перевозимого с i-й базы j-му магазину. Тогда общие затраты, связанные с реализацией плана перевозок представятся целевой функцией Или.

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

(для 1-й базы).

(для 2-й базы).

(для 3-й базы).

(для 4-й базы) Аналогично, потребности каждого магазина должны быть удовлетворены, то есть должны выполняться равенства:

(для 1-го магазина).

(для 2-го магазина).

(для 3-го магазина).

(для 4-го магазина).

(для 5-го магазина) Объем перевозок товара не может быть отрицательным, поэтому (,).

3) Транспортная задача разрешима только в том случае, когда выполняется условие баланса:. В нашем случае оно нарушено, так как,. Следовательно, задача является открытой, несбалансированной. Так как, то введем фиктивный магазин, потребности в товаре которого составляют тыс.ед. Согласно условию необходимо полностью освободить 3-ю базу, следовательно, стоимость транспортных расходов на доставку 1 тыс.ед. товара с 3-й базы в фиктивный магазин необходимо сделать невыгодной, например,. Пусть. А стоимость транспортных расходов на доставку 1 тыс.ед. товара с остальных баз в фиктивный магазин будем полагать равной нулю,,. Получим следующую закрытую модель транспортной задачи:

.

(,).

4) Построим начальный опорный план задачи методом «минимального элемента». Для этого найдем наименьший элемент матрицы тарифов (выбираем только среди стоимостей реальных баз и магазинов, а потребности фиктивного магазина удовлетворим в последнюю очередь). Он находится в клетках (3,1) и (1,3):, , и так далее. Получим.

Проверим условие для базисных клеток (их должно быть п+m-1): п+m-1=4+6−1=9. Заполнено также 9 клеток. Следовательно, начальный опорный план построен верно. При этом значение целевой функции будет равно:

(ден.ед.).

5) Вычислим потенциалы и. Для базисных клеток: .

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

(ден.ед.).

(ден.ед.).

(ден.ед.).

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

(ден.ед.).

6) Итак, чтобы привезти товар с минимальными затратами 359 (ден.ед.), необходимо с первой базы в 1-й, 3-й и 5-й магазины доставить 10, 18 и 2 тыс.ед. товара соответственно, со 2-й базы во 2-й и 4-й магазины доставить 20 и 5 тыс.ед. товара соответственно, с 3-й базы в 5-й магазин доставить 20 тыс. ед товара, с 4-й базы — в 4-й и 5-й магазины доставить 7, 3 тыс.ед. товара соответственно. Наличие 5 тыс.ед. товара в фиктивном магазине свидетельствует о том, что при условии полного удовлетворения потребностей всех магазинов, четвертая база не будут освобождена полностью, там останется 5 тыс.ед. товара.

Задание 3. Предприятие планирует открыть филиалы в Михайловке, Урюпинске и Котельниково, для чего выделяются средства в размере 5 млн руб. По расчетам экономистов, каждый филиал при инвестировании в него х тыс.руб. приносит прибыль тыс.руб. Эти данные приведены в таблице:

Необходимо выбрать оптимальное распределение выделенных средств между филиалами, обеспечивающее максимальную прибыль всего проекта.

Решение:

• 1. Построение экономико-математической модели задачи.
• 1.1. Число шагов равно числу филиалов m=3.
• 1.2. Состояние системы на каждом шаге будем характеризовать количеством средств S, имеющихся в наличии перед очередным шагом.
• 1.3. — количество средств, инвестируемых в i-ый филиал.
• 1.4. Выигрыш на i-ом шаге определяется формулой. Это прибыль, которую приносит i-ый филиал при инвестировании в него средств .

Общая прибыль всего проекта, естественно, составит:

• 1.5. Если в наличии имеются средства S, и в i-ый филиал вложено х тыс.руб., то для дальнейшего инвестирования остается (Sх) тыс.руб. Эту фразу можно сформулировать иначе на языке динамического программирования: если на i-ом шаге система находится в состоянии S, и выбрано управление х, то на (i+1)-ом шаге система окажется в состоянии (Sх). Таким образом, функция перехода в новое состояние имеет вид:
• 1.6. Обозначим через выигрыш с i-го шага до конца процесса при условии, что к началу i-го шага система находится в состоянии S. Например, — прибыль, получаемая от вложения 3 млн руб. во 2 и 3 филиалы.
• 1.7. Составим функциональное уравнение — уравнение, выражающее через. Функциональное уравнение выражает оптимальный выигрыш для данного состояния S с i-го шага до конца процесса через известный оптимальный выигрыш с (i+1)-го шага до конца процесса. Сначала составим функциональное уравнение для i=m, т. е. последнего шага. Для этого заметим, что на последнем шаге, т. е. перед инвестированием в последний филиал, оптимальное управление соответствует количеству оставшихся в наличии средств, т. е. сколько денег осталось, столько и вкладываем в 3-ий филиал. Выигрыш при этом равен доходу последнего филиала от вложения в него оставшихся средств:

.

.

Перейдем к составлению основного функционального уравнения.

Пусть перед инвестированием средств в i-ый филиал осталось S млн.руб. Тогда х млн.руб. можно вложить в i-ый филиал, и он принесет прибыль. Оставшиеся (S-х) млн.руб. вкладываются в остальные филиалы с (i+1)-го до m-го, которые принесут прибыль. Оптимальным будет такое управление, при котором.

.

Отсюда получаем основное функциональное уравнение:

.

Например, при i=1 уравнение примет вид:

.

Это, что в первый филиал надо вложить столько средств, чтобы сумма прибыли, приносимой им и оставшимися 2-м и 3-м филиалами, была максимальна.

2. Условная оптимизация.

Результаты вычислений будем заносить в сводную таблицу: в первом столбце записываем возможные состояния системы (S=1, 2, 2, 4, 5), в верхней строке (шапке) — номера филиалов, соответствующие номеру шага (i=1, 2,3). На каждом шаге определяем условные оптимальные управления и соответствующие им выигрыши .

2.1. Условная оптимизация для i=3.

В соответствие с принципом оптимальности Беллмана, лежащего в основе методов динамического программирования, условную оптимизацию начинаем с последнего шага, т. е. с 3-го филиала.

Функциональное уравнение имеет вид:

.

.

Поэтому столбцы для i=3 заполняем автоматически на основе исходной таблицы. В последнем филиале — сколько средств осталось, столько и вкладываем. Получаем таблицу условной оптимизации № 1:

2.2. Условная оптимизация для i=2.

Функциональное уравнение имеет вид:

.

Это означает, что во второй филиал надо вложить столько средств, чтобы сумма прибыли, полученной от него от 3-го филиала была максимальна.

Необходимо рассмотреть пять случаев.

Случай S=1:

следовательно,, .

Случай S=2:

следовательно,, .

Случай S=3:

следовательно,, .

Случай S=4:

следовательно,, .

Случай S=5:

следовательно,, .

Полученные результаты заносим в таблицу и получаем сводную таблицу условной оптимизации № 2:

2.3. Условная оптимизация для i=1.

Функциональное уравнение имеет вид:

.

Т.е. в первый филиал надо вложить столько средств, чтобы сумма прибыли, полученной от него и от 2-го и 3-го филиалов, была максимальна. Поскольку этот филиал первый, то мы располагаем всей суммой S=D=5 млн руб. Поэтому условную оптимизацию проводим только для S=5.

следовательно,, .

Полученные результаты заносим в таблицу и получим сводную таблицу условной оптимизации № 3:

3. Безусловная оптимизация.

Проводим безусловную оптимизацию в «прямом» порядке — от 1-го к 3-му филиалу.

1). В первый филиал надо вложить млн.руб., в результате чего для 2-го и 3-го филиалов остаётся 1 млн руб.

2). Во второй филиал надо вложить млн.руб., в результате чего для 3-го …