2.1 Поиск оптимального значения проблемного параметра

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

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

Вычислим минимальное требуемое значение коэффициента загрузки автомашины:

Для наглядности, представлен график зависимости прибыли от расстояния, на которое совершается доставка при текущем значении коэффициента загрузки автомашины и при значении после оптимизации (рисунок 6). Штриховкой обозначена область, которая показывает на какие расстояния в основном доставляются грузы.

Рисунок 6. – График зависимости прибыли от расстояния доставки.

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

Математическая модель процесса формирования автомашины с грузом «как есть».

В качестве метода математического моделирования была выбрана задача «О ранце», так как ее решение позволяет наглядно и достаточно подробно представить рассматриваемый процесс.

Задача «О ранце» - одна из NP-задач комбинаторной оптимизации. Своё название получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена.

В общем виде задачу в её классическом варианте можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

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

Математически задачу можно сформулировать так: имеется n грузов. Для каждого i-го груза определён вес w_i > 0 и ценность v_i>0, i= 1,2,...,n. Дана грузоподъёмность W. Необходимо выбрать подмножество грузов так, чтобы их общий вес не превышал W, а суммарная их ценность была бы максимальной.

Исходные данные.

Автомашина загружается предметами N различных типов (табл) с весом w_j и стоимостью c_j, j = 1,n. Максимальная грузоподъемность равна W=5. Определить максимальную стоимость груза, вес которого не более W. 

Таблица 2 - Исходные данные

Тип j	Вес wj	Стоимость cj
1	2	65
2	3	80
3	1	30

Решение.

Сделаем математическую постановку. Пусть n_j – количество предметов j-го типа, загружаемых в автомашину. Тогда математическая модель имеет вид: 

Отличительными особенностями задачи динамического программирования будут: 

1. Этап j связан с загрузкой предметов j-го типа в количестве x_j единиц (x_j – управляемая переменная); 

2. Состояние загружаемой автомашины S_j на этапе j определяется через ограничение математической модели.

0 ≤ S_j ≤ W;

S_n = W 

3. Цель управления на этапе z_j = c_jxj.  4. Варианты решения x_j этапа j описываются количеством предметов типа j: 

Решим задачу методом обратной прогонки, загружая предметы с последнего типа. Пусть F_j(S_j) – значение целевой функции (максимальная стоимость предметов, включенных на этапах j,  j=1, .. , n, при заданном состоянии системы S_j

Рекуррентное соотношение для процедур обратной прогонки: 

Этап 1.  F₃(S₃) = max{ c_3x3};  x₃ = 0,1,..,5;  S₃ = 0,1,…,5;  S₃ ≥ 1x3.

Таблица 2 – Первый этап

S3	c3x3							opt
	x3=0	x3=1	x3=2	x3=3	x3=4	x3=5	F3*(S3)		x3*
0	0	–	–	–	–	–	0		0
1	0	30	–	–	–	–	30		1
2	0	30	60	–	–	–	60		2
3	0	30	60	90	–	–	90		3
4	0	30	60	90	120	–	120		4
5	0	30	60	90	120	150	150		5

Этап 2.

F₂(S₂) = max{c₂x₂ + F₃(S₂ – w₂x₂)}  x₂ = 0,1  S₂ = 0,1,..,5  S₂ ≥ 2x₂

Таблица 3 – Второй этап

S2	c2x2 + F3(S2 – w2x2)			opt
	x2=0	x2=1	F2*(S2)		x2*
0	0 + 0 = 0	–	0		0
1	0 +30 = 30	–	30		0
2	0 + 60 = 60	–	60		0
3	0 + 90 = 90	80 + 0 = 80	90		0
4	0 + 120 = 120	80 + 30 = 110	120		0
5	0 + 150 = 150	80 + 60 = 140	150		0

Значение условного оптимума F3(S₃) берется из предыдущей таблицы. 

Этап 3.

F₁(S₁) = max{c₁x₁ + F₂(S₁ – w₁x₁)};  x₁ = 0,1,2;  S1=5.

Таблица 4 – Третий этап

S1	c1x1 + F2(S1 – w1x1)			opt
	x1=0	x1=1	x1=2	F1*(S1)	x1*
5	0 + 150 = 150	65 + 90 = 155	130 + 30 +160	160	2

Определение управляемых переменных начинается с последней таблицы (обратный ход):  x_1* = 2 → S₁ = 2*2 = 4  S₂ = 5-4 =1 → x₂ = 0 → S₃ = 1 – 0 = 1 → x₃ = 1  Оптимальное решение X^* = (2,0,1)