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

Вариант 1.

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

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

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

Вариант 2.

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

Завод	Транспортные издержки, т. руб. за тонну до торгового склада №	Предложение, тонн
А
В
С
Потребность, тонн

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

Вариант 3

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

Пекарня	Транспортные издержки, тыс. руб. за тонну до магазина №	Общее предложение тонн
X	1,5	2,5	1,0	2,0
Y	2,0	3,0	2,0	1,5
Z	1,0	1,5	2,5	3,0
Общая потребность

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

Вариант 4

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

Завод	Транспортные издержки, тыс. руб. за тонну до торгового склада №	Предло-жение, т.
А
В
С
Потребность, т

Требуется определить минимальную стоимость транспортировки на январь.

9. Динамическое программирование

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

Алгоритм многошаговой оптимизации методом динамического про­граммирования содержит следующие этапы.

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

2. Определяются функции эффекта (выигрыша) на i-м шаге в зависи­мости от состояния системы в начале этого шага S_i, и используются уп­равления U_i:w_i =w_i(S_i, U_i).

3. Определяются функции, выражающие изменение состояния S_i, сис­темы под влиянием управления U_i на i-м шаге процесса: S_i * =φ(S_i, U_i).

4. Составляется основное рекуррентное соотношение динамического программирования: W_i(S_i) = opt{ w_i(S_i, U_i) + W_i+1 (φ(S_i, U_i))}

5. Определяется условно-оптимальный эффект (выигрыш) для послед­него n-го шага рассматриваемого процесса: W_n(S_n), а также соответству­ющее ему условно-оптимальное управление U_i *.

6. Определяются условные оптимальные выигрыши (эффекты) и соответствующие этим эффектам управления для предпоследнего, предпредпоследнего и т. д. до первого шагов процесса:

W₁(S₁) = opt{ w₁(S₁, U₁) + W₂ (S₂)}.

7. Определяется начальное состояние (если оно не задано), выбира­ются оптимальные эффекты и безусловные управления для первого, второго и т. д. до последнего n-го шага рассматриваемого процесса.

После выполнения работы студент должен:

ЗНАТЬ:

- принцип оптимальности в динамическом программировании;

УМЕТЬ:

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

ВЛАДЕТЬ:

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