Пример выполнения задания.

Содержательная постановка задачи. Имеется ранец с максимально допустимой массой 50кг. Дано 5 видов предметов, при этом один предмет j‑го вида имеет цену z_j (у.е.) и массу w_j (кг).

Вид предмета	1	2	3	4	5
масса 1 предмета (wj )	3	4	2	6	2
ценность 1 предмета (zj)	3	4	1	5	2

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

Математическая модель задачи. Обозначение вводится следующим образом: пусть x_j – количество предметов j‑го вида, загруженных в ранец, . N=5.

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

.

Ограничение на допустимую массу запишется как

, где М=50.

Ограничения на переменные (физический смысл): .

Получаем следующую математическую модель задачи:

;

;

Данная математическая модель с учетом исходных данных перепишется:

3х₁+4х₂+1х₃+5х₄+2х₅max

3 х₁+ 4 х₂+ 2 х₃+ 6 х₄ +2 х₅ ≤ 50

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

Здесь - вес рюкзака перед погрузкой грузов j-того вида (текущий вес), - вес рюкзака до начала погрузки. В терминах поставленной задачи:

3х₁+4х₂+1х₃+5х₄+2х₅max

y₂=y₁+3 х₁

y₃=y₂+4 х₂

y₄=y₃+2 х₃

y₅=y₄+6 х₄

y₆=y₅+2 х₅

y₁=0

0≤ х₁≤(50- y₁)/3

0≤ х₂≤(50- y₂)/4

0≤ х₃≤(50- y₃)/2

0≤ х₄≤(50- y₄)/6

0≤ х₅≤(50- y₅)/2

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

х₁=0, х₂=0, х₃=0, х₄=0, х₅=25. y₆=50, F=50.

Данные результаты означают следующее: в рюкзак следует погрузить только 25 единиц груза пятого вида. При этом вес рюкзака составит 50 кг, а ценность 50 у.е.

Описание работы с программой Dinamic.

Программа предназначена для решения целочисленных задач с сепарабельной целевой функцией типа задачи о загрузке рюкзака методом динамического программирования. Запуск исполняемого файла Dinamic.exe активизирует диалоговое окно, в которое вводятся исходные данные задачи: количество видов помещаемых в рюкзак грузов (кнопка «Изменить» служит для формирования пустых таблиц для ввода всех последующих данных с учетом указанного количества), весов единицы груза каждого вида, грузоподъемности рюкзака и ценности помещаемых в него грузов(Рис.1). Данные вводятся студентом в соответствии с сформированной им мат. моделью.

Рис. 1

Нажав кнопку «Вычислить», студент запускает процесс вычислений. Каждая итерация вычислений отражается в отдельной таблице (Рис. 2).

Рис. 2

Последняя таблица содержит результаты обратного прохода алгоритма – решение задачи (Рис. 3).

Рис. 3

Все таблицы по каждому этапу вычислений доступны и после завершения расчетов, что упрощает проверку работы преподавателем и понимание сущности алгоритма студентом (Рис. 4).

Рис. 4

Вариант № 1. Задача о погрузке контейнеров.

Контейнер	1	2	3	4	5	6
Площ. vj	20	40	17	38	55	29
Ценность uj	120	150	110	180	220	165

Корабль имеет на палубе свободное место площадью 100 м² для погрузки контейнеров. Дано 6 типов контейнеров, таких, что каждый контейнер j‑го типа занимает площадь v_j (см. таблицу) и обладает ценностью u_j , Требуется определить, какие контейнеры в каком количестве следует погрузить на корабль, чтобы суммарная ценность контейнеров была максимальной при ограничении на площадь на палубе корабля.

Вариант № 2. Задача о строительстве домов.

Заказ	Прибыль sj
1	12
2	14
3	10
4	22
5	13

Строительная организация имеет запас кирпичей в количестве 100 млн. Имеется 5 проектов домов, при этом j‑й проект требует r_j  млн. кирпичей. Прибыль от строительства одного дома по j‑му проекту составит s_j млн. руб. , (см. таблицу).

Заказ	1	2	3	4	5
Ресурсы rj	39	34	19	42	46

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

Вариант № 3. Задача о выпуске обуви.

Вид обуви	1	2	3	4	5
Расход ej	36	48	13	36	51
Прибыль hj	1200	1500	950	1800	2000

На обувном предприятии имеется материал в количестве 100 единиц. Предложено выпускать 5 видов обуви, при этом на изготовление одной пары обуви j‑го вида требуется e_j единиц материала, а прибыль от реализации одной пары составит h_j , Требуется определить, какие виды обуви следует выпустить, чтобы суммарная прибыль была максимальной при ограничении на имеющийся у обувного предприятия объём материала.

Вариант № 4. Задача о перевозке грузов.

Имеется транспортное судно грузоподъемностью 200 единиц. На это судно необходимо погрузить: бочки с сельдью (вес бочки 35 ед., стоимость 500 руб.), ящики с гвоздями (вес ящика 45 ед., стоимость 1000 руб.), мешки с солью (вес мешка 34 ед., стоимость 500 руб.) и цистерны с керосином (вес 56 ед., стоимость 600руб.). Требуется определить, какой груз и в каком количестве следует погрузить, чтобы общая стоимость перевезенного груза была максимальна, и при этом не была превышена грузоподъемность.

Вариант № 5. Задача о печати книг.

Книга	1	2	3	4	5
Расход бумаги cj	70	67	51	56	58
Цена книги dj	80	100	120	140	150

В типографии имеется 1000 листов бумаги. Для печати определены 5 наименований книг, при этом на одну j‑ю книгу расходуется c_j листов, а прибыль от её продажи составит d_j , . Требуется определить, какие книги, в каком количестве следует напечатать, чтобы суммарная прибыль от их продажи была максимальной при ограничении на имеющийся у типографии запас бумаги.

8