Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок


Скачать 192.42 Kb.
НазваниеЛабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок
Дата публикации06.05.2013
Размер192.42 Kb.
ТипЛабораторная работа
userdocs.ru > Информатика > Лабораторная работа
Лабораторная работа № 6.

Тема: Решение задачи о загрузке методом динамического программирования.
Цель работы: Получить практические навыки по обоснованию оптимальности загрузки.
Порядок выполнения работы:


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

  2. Решить задачу динамического программирования в соответствии со своим вариантом.

  3. Сделать выводы.


Методические указания к выполнению задания.
Рассмотрим применение метода динамического программирования на примере распределения грузов между 4-мя торговыми суднами. Пусть общая вместимость торговых суден составляет не более 500 тонн. На основе технико-экономических расчетов установлено стоимость перевозки каждым судном определенного количества груза, которая приведена в таблице 1. Необходимо определить оптимальное распределение грузов между суднами, обеспечивающее минимизацию затрат предприятий. Таким образом, в этой оптимизационной задаче используется критерий – суммарная стоимость загрузки.

Таблица 1.




Вместимость торговых суден (тонн)

№ торгового судна

0

100

200

300

400

500




Стоимость перевозки (тыс. грн.)

1

400

500

550

700

750

1000

2

4000

4200

4300

4500

4600

4700

3

0

100

400

800

850

900

4

600

750

900

950

1100

1200

Пусть х1, х2, х3, х4 вместимость соответственно первого, второго, третьего и четвертого судна, 0 хi 5, i = 1,4. Обозначим f1(x), f2(x), f3(x), f4(x) функции изменения стоимости перевозки первого, второго, третьего и четвертого предприятия при из загрузке х тыс.тонн. Этим функциям соответствуют строки 1, 2, 3, 4 в табл.1.

Определим минимум функции цели

F (х1, х2, х3, х4) = f1(x) + f2(x) + f3(x) + f4(x) min.

При этом на объемы загрузки х1, х2, х3, х4 наложены ограничения

х1 + х2 + х3 + х4 = А,

тыс.тонн.

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

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

Выделим в нашей задаче 3 шага:

  1. А тыс. тонн загружаются в первое, второе судно одновременно;

  2. А тыс. тонн загружаются в первое, второе, третье судно вместе;

  3. А млн. тонн. загружаются в четыре судна одновременно.

Обозначим: F1,2 (А), F1,2,3 (А), F1,2,3,4 (А) соответственно оптимальные распределения грузов для первого, второго и третьего шагов.

Алгоритм метода динамического программирования состоит из двух этапов. На первом этапе выполняется условная оптимизация, заключающаяся в том, что для каждого из трех шагов находят условный оптимальный выигрыш F1,2 (А), F1,2,3 (А), F1,2,3,4 (А). На втором этапе выполняется безусловная оптимизация. Используя результаты первого этапа, находят величины загрузки торговых суден х1, х2, х3, х4, обеспечивающие минимальную стоимость перевозки.

Первый этап включает следующие шаги:

1) Вычисление максимума критерия оптимизации для различных значений по объемам загрузки х = 0, 100, 200, 300, 400, 500, которые используются только для суден 1 и 2. Расчет ведется по формуле

F1,2 ( А ) = min [ f1( x ) + f2 ( A - x ) ];

0 x 500;

0 A 500.

Результаты расчета представлены в табл.2.
Таблица2.







х2 = А - х

х1

f1( x )

0

100

200

300

400

500







f2( А - x )







4000

4200

4300

4500

4600

4700

0

400

4400

4600

4700

4900

5000

5100

100

500

4500

4700

4800

5000

5100




200

550

4550

4750

4850

5050







300

700

4700

4900

5000










400

750

4750

4950













500

1000

5000

















Например, для того, чтобы определить F1,2 ( 2 ), надо вычислить
f1( 2 ) + f2 ( 0 ) = 550 + 4000 = 4550;

f1( 1 ) + f2 ( 1 ) = 500 + 4200 = 4700;

f1( 0 ) + f2 ( 2 ) = 400 + 4300 = 4700.

Наименьшее из полученных значений будет 4400. Остальные F1,2 ( х ) получаются как наименьшее значение каждой диагонали в таблице ( эти значения в таблице подчеркнуты:
F2 ( 0 ) = min (4400) = 4400;

F2 ( 1 ) = min ( 4500, 4600) = 4500;

F2 ( 2 ) = min ( 4550, 4700, 4700) = 4550;

F2 ( 3 ) = min ( 4700, 4750, 4800, 4900) =4700;

F2 ( 4 ) = min ( 4750, 4900, 4850, 5000, 5000) =4750;

F2 ( 5 ) = min (5000, 4950, 5000, 5050, 5100)=4950.
2) Вычисление минимума критерия оптимизации для различных значений по объемам загрузки х = 0, 100, 200, 300, 400, 500, которые используются только для торговых суден 1,2 и 3.

Расчет ведется по формуле

F1,2,3 ( А ) = min [ F1,2( A ) + f3 ( A - x ) ];

0 x 500;

0 A 500.

Результаты расчетов занесем в табл.3, которая аналогична табл.2, только вместо f1( x ) в ней указаны значения F2 ( А ), а f2 ( A - x ) заменена на f3 ( A - x ).

Таблица3.







х3 = А - х

A

F1,2(A)

0

100

200

300

400

500







f3( А - x )







0

100

400

800

850

900

0

4400

4400

4500

4800

5200

5250

5300

100

4500

4500

4600

4900

5300

5350




200

4550

4550

4650

4950

5350







300

4700

4700

4800

5100










400

4750

4750

4850













500

4950

4950
















Значения F1,2,3 ( A ) будут следующими:

F1,2,3 ( 0 ) = 4400; F1,2,3 ( 1 ) = 4500; F1,2,3 ( 2 ) = 4550;

F1,2,3 ( 3 ) = 4650; F1,2,3 ( 4 ) = 4750; F1,2,3 ( 5 ) = 4850.

3) Вычисление минимума критерия оптимизации по объемам загрузки х = 0, 100, 200, 300, 400, 500, которые используются для всех торговых суден.

Расчет ведется по формуле

F1,2,3,4 ( А ) = min [ F1,2,3( A ) + f4 ( A - x ) ];

0 x 500;

0 A 500.

Результаты расчетов заносим в табл.4.

Таблица4.







х4 = А – х

A

F1,2,3(А)

0

100

200

300

400

500







f4( А - x )







600

750

900

950

1100

1200

0

4400

5000

5150

5300

5350

5500

5600

100

4500

5100

5250

5400

5450

5600




200

4550

5150

5300

5450

5500







300

4650

5250

5400

5550










400

4750

5350

5500













500

4850

5450

















Значения F1,2,3,4 ( А ) в результате расчета будут следующими:

F1,2,3,4 ( 0 ) = 5000; F1,2,3,4 ( 1 ) = 5100;

F1,2,3,4 ( 2 ) = 5150; F1,2,3,4 ( 3 ) = 5250;

F1,2,3,4 ( 4 ) = 5350; F1,2,3,4 ( 5 ) = 5450.

На этом первый этап решения задачи динамического программирования заканчивается.

Перейдем ко второму этапу решения задачи динамического программирования безусловной оптимизации. На этом этапе используются табл.4,3,2. Определим оптимальные объемы загрузки суден для А = 0, 100, 200, 300, 400, 500. Для этого выполним следующие расчеты.

  1. Пусть объем загрузки всех суден составляет А = 500 тис. тонн.

Определим объем загрузки четвертого судна. Для этого используем табл. 4. Выберем на ней диагональ, соответствующую А = 500 это значения 5450, 5500, 5550, 5500, 5600, 5600. Из этих чисел возьмем минимальное F1,2,3,4 ( 5 ) = 5450 тыс. грн. Отмечаем столбец, в котором стоит эта величина. Далее определяем в отмеченном столбце объем загрузки четвертого судна х4 = 0.

На загрузку первого, второго и третьего судна остается

А = 500 - х4 = 500 тыс. тонн.

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

Для этого используем табл.3. Выберем в этой таблице диагональ, соответствующую А = 500 это значения 4950, 4850, 5100, 5350, 5350, 5300. Отмечаем столбец, в котором стоит минимальная величина стоимости F1,2,3 ( 4 ) = 4850 тыс. грн. Определяем значение х4 = 100 тыс. тон. в отмеченном столбце.

  1. На загрузку первого и второго судна остается сумма

А = 5 - х4 - х3 =400 тыс. тонн.

Определим объем загрузки второго судна. Используем для этого табл.2. Выберем в таблице диагональ, соответствующую А = 400 это значения 4750, 4900, 4850, 5000, 5000. Отмечаем столбец с минимальной величиной стоимости F1,2 ( 1 ) = 4750 тыс. грн. Тогда в этом столбце х2 =0 тыс. тонн.

  1. Определим объем загрузки первого судна. А=500-100=400 тыс. тонн.

Таким образом, для объема груза в А = 500 тыс. тонн. оптимальным является загрузка первого судна на 400 тыс. тон, а третьего на 100 тыс. тон. Загружать второе и четвертое судно экономически не выгодно. При этом суммарная стоимость загрузки 750+100=850 тыс. т.

^

Указания к выполнению работы

Определить оптимальную загрузку 4-х торговых суден по критерию минимальной стоимости общей вместимостью:

  1. ^

    400 тыс. тонн.


  2. 300 тыс. тонн.

Для первого этапа решения задачи, заполнить нижеприведенную таблицу в соответствии со своим вариантом (№ по списку).





Вместимость торговых суден (тыс.тонн)

№ торгового судна

0

100

200

300

400




Стоимость перевозки (тыс. грн.)

1
















2
















3
















4


















^

Варианты заданий


fi(x)- минимизация стоимости загрузки, тыс.грн.

Для различных вариантов значения fi (x), i=1,...5 задаются с помощью матрицы
F=

Вариант 1 Вариант 2 Вариант 3

F= F= F=

Вариант 4 Вариант 5 Вариант 6

F= F= F=

Вариант 7 Вариант 8 Вариант 9

F= F= F=

Вариант 10 Вариант 11 Вариант 12

F= F= F=
Вариант 13 Вариант 14 Вариант 15

F= F= F=

Вариант 16 Вариант 17 Вариант 18

F= F= F=

Вариант 19 Вариант 20 Вариант 21

F= F= F=

Вариант 22 Вариант 23 Вариант 24

F= F= F=

Вариант 25 Вариант 26 Вариант 27

F= F= F=

Вариант 28 Вариант 29 Вариант 30
F= F= F=

Вариант 31 Вариант 32
F= F=

Похожие:

Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconЛабораторная работа №1
Цель работы: приобрести навыки работы в системе программирования на примере интегрированной среды tp
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconЛабораторная работа №5
Цель работы: получить навыки работы по созданию, редактированию и расчетам с помощью электронных таблиц
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconЛабораторная работа №6 Работа с отчетами
Получить практические навыки работы с отчетами в бд microsoft Office Access 2003, научиться создавать отчеты и задавать параметры...
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconЛабораторная работа №1 Построение и реализация моделирующих алгоритмов...
Цель работы: выработка навыков алгоритмизации и программирования имитационных моделей систем массового обслуживания (смо) методом...
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconЛабораторная работа № Решение системы уравнений заданным методом
Получить устойчивые навыки использования диапазонов, массивов, матричных операций для обработки статистических данных и решения систем...
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconЛабораторная работа №3 Работа с данными в таблицах
Получить практические навыки работы с данными в бд microsoft Office Access 2003, научиться применять фильтры для отбора необходимых...
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconРешение задачи включает пять этапов
Получить практические навыки работы с запросами в бд microsoft Office Access 2003, научиться создавать запросы при помощи мастера...
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconЛабораторная работа №4 Добавление вычисляемого поля
...
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconТема : Фигуры в ms visio
Цель работы: получить представление о фигуре как об объекте ms visio, получить понятие о одномерных, двумерных и трехмерных фигурах,...
Лабораторная работа № Тема: Решение задачи о загрузке методом динамического программирования. Цель работы: Получить практические навыки по обоснованию оптимальности загрузки. Порядок iconЛабораторная работа №3 тема: Определение влажности почвы
Перед выполнением лабораторной работы студент должен получить допуск к выполнению работы у
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница