Пример выполнения работы

Содержательная постановка задачи. Автогараж располагает 3 видами грузовых машин: А, Б и В грузоподъемностью 5т, 4т и 3т соответственно. Одна машина типа А тратит на выполнение работы 60л бензина, типа Б - 30л, типа С - 20л. Найти число машин, исходя из следующих условий:

• затраты бензина не превосходят 3000л ,

• объем перевозок не менее 300т ,

• суммарное количество машин минимально.

Анализ словесного описания задачи

Управляемые параметры: количество машин каждого вида Неуправляемые параметры: грузоподъемность каждой машины и расход бензина Целевые параметры: суммарные затраты бензина, суммарный объем перевозок суммарное количество используемых машин

Построение математической модели

Характеристика машины	Машина типа А	Машина типа Б	Машина типа В
Грузоподъемность, т	5	4	3
Расход бензина	60	30	20

Условные обозначения:

Управляемые параметры: X₁,X₂,X₃ - количество машин типа А,Б и В соответственно, т.е. количество неизвестных равно 3.

Целевые параметры: F₃ - количество используемых машин.

Ограничиваемые параметры:

• W₁ - затраты бензина,

• W₂ - объем перевозок,

т.е. количество ограничений равно 2. Неуправляемые параметры: a_1,1=60 a_1,2=30 a_1,3=20 a_2,1=5 a_2,2=4 a_2,3=3 Соотношения между параметрами: W₁ = 60X₁+30X₂ +20X₃ W₂ = 5X₁ + 4X₂ + 3X₃ F₃ = X₁ + X₂ + X₃

Формирование задачи выбора наилучшей стратегии

Искомые параметры: X₁ , X₂ , X₃ Целевая функция: F(X) = X₁ + X₂ +X₃ => min Ограничения:

60X₁ +30X₂ +20X₃ ≤ 3000 5X₁ +4X₂ +3X₃  300 X_i ≥0 - целые, (i=1,3)

Решение данной задачи.

Введем сформированную модель в программу LDPTechs и решим ее симплекс-методом без учета целочисленности. Получим следующий результат:

Это означает, что решением является план (33¹/₃; 33¹/₃; 0), , и значение целевой функции при этом 66²/₃.

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

G0	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 Xi ≥0 (i=1,3)
Решение: (331/3; 331/3; 0), F=662/3.

разбивается на две:

G11

F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 (-целая часть компоненты Х*1=33,3) Xi ≥0 (i=1,3)

G12

F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1  34 (-целая часть компоненты Х*1=33,3 плюс 1) Xi ≥0 (i=1,3)

Решаем обе эти задачи при помощи той же программы LDPTechs. Первую (G¹₁):

И вторую (G¹₂):

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

G0	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 Xi ≥0 (i=1,3)
Решение: (331/3; 331/3; 0), F=662/3.

G11	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 (-целая часть компоненты Х*1=33,3) Xi ≥0 (i=1,3)	G12	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1  34 (-целая часть компоненты Х*1=33,3 плюс 1) Xi ≥0 (i=1,3)
Решение: (33; 33 3/4; 0), F=66 ¾.		Решение: (34; 28; 6), F=68.

На множестве G¹₂ полученный план – целый, однако оценка нижней границы (значение целевой функции) выше, чем на множестве G¹₁ (F(G¹₁)=66¾ < F(G¹₂)=68). Поэтому план (34; 28; 6) не является оптимальным. План же множества G¹₁ не целый, поэтому необходимо продолжить ветвление множества G¹₁ относительно нецелочисленной компоненты плана (33; 33 ³/₄; 0), т.е. относительно Х₂ =33 ³/₄. Получим:

G0	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 Xi ≥0 (i=1,3)
Решение: (331/3; 331/3; 0), F=662/3.

G11	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 Xi ≥0 (i=1,3)	G12	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1  34 Xi ≥0 (i=1,3)
Решение: (33; 33 3/4; 0), F=66 ¾.		Решение: (34; 28; 6), F=68.

G111

F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2 ≤ 33 Xi ≥0 (i=1,3)

G112

F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2  34 Xi ≥0 (i=1,3)

Перенумеровав полученные множества: G¹₁₁= G²₁, G¹₁₂= G²₂, G¹₂= G²₃, введем данные задач G²₁ и G²₂ в программу LDPTechs и решим их:

Для G²₁:

Для G²₂:

Отразим решение в дереве:

G0	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 Xi ≥0 (i=1,3)
Решение: (331/3; 331/3; 0), F=662/3.

G11	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 Xi ≥0 (i=1,3)	G23	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1  34 Xi ≥0 (i=1,3)
Решение: (33; 33 3/4; 0), F=66 ¾.		Решение: (34; 28; 6), F=68.

G21	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2 ≤ 33 Xi ≥0 (i=1,3)	G22	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2  34 Xi ≥0 (i=1,3)
Решение: (33; 33; 1), F=67		Решение: (32 4/5; 34; 0), F=66 4/5.

Минимальное значение целевой функции достигается на множестве G²₂, соответствующий план – не целый. Продолжаем ветвление: ветвим множество G²₂ относительно компоненты Х₁=32 ⁴/₅.

G0	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 Xi ≥0 (i=1,3)
Решение: (331/3; 331/3; 0), F=662/3.

G11	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 Xi ≥0 (i=1,3)	G23	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1  34 Xi ≥0 (i=1,3)
Решение: (33; 33 3/4; 0), F=66 ¾.		Решение: (34; 28; 6), F=68.

G21	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2 ≤ 33 Xi ≥0 (i=1,3)	G22	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2  34 Xi ≥0 (i=1,3)
Решение: (33; 33; 1), F=67		Решение: (32 4/5; 34; 0), F=66 4/5.

G221

F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2 ≤ 33 X1 ≤ 32 Xi ≥0 (i=1,3)

G221

F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2  34 X1  33 Xi ≥0 (i=1,3)

Перенумеровываем: G²₃= G³₁, G²₁= G³₂, G²₂₁= G³₃, G²₂₂= G³₄ введем данные в программу LDPTechs и решим их:

Для G³₃:

Для G³₄:

G0	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 Xi ≥0 (i=1,3)
Решение: (331/3; 331/3; 0), F=662/3.

G11	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 Xi ≥0 (i=1,3)	G31	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1  34 Xi ≥0 (i=1,3)
Решение: (33; 33 3/4; 0), F=66 ¾.		Решение: (34; 28; 6), F=68.

G32	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2 ≤ 33 Xi ≥0 (i=1,3)	G22	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2  34 Xi ≥0 (i=1,3)
Решение: (33; 33; 1), F=67		Решение: (32 4/5; 34; 0), F=66 4/5.

G33	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2 ≤ 33 X1 ≤ 32 Xi ≥0 (i=1,3)	G34	F(X) = X1 + X2 +X3 => min 60X1 +30X2 +20X3 ≤ 3000 5X1 +4X2 +3X3  300 X1 ≤ 33 X2  34 X1  33 Xi ≥0 (i=1,3)
Решение: (32; 35; 0), F=67		Решение: (33; 34; 0), F=67

Минимальное значение целевой функции F= 67 достигается сразу на трех множествах: G³₂, G³₃, G³₄. На всех трех множествах полученные планы – целочисленные. Поэтому в качестве решения можно выбрать любое из:

(33; 33; 1), (32; 35; 0), (33; 34; 0). К примеру, возьмем первое.

Если бы при равных значениях F некоторые планы были бы не целые, то в качестве решения мы выбрали бы целочисленное.

В терминах постановки задачи данные результаты могут быть интерпретированы следующим образом: необходимо использовать 33 машины типа А, 33 машины типа Б и одну машину типа В. Суммарное количество машин при этом – 67 штук.