Поставить задачу линейного программирования и найти оптимальное решение в ситуации: «Грузоперевозчик покупает автомобили. Бюджет покупки – 150 д.е. Цена 3-тонного автомобиля составляет 4 д.е., 5-тонного – 5 д.е. Возможности грузоперевозчика по техническому обслуживанию автомобилей – не более 20 единиц 3-тонных автомобилей сразу и не более 18 единиц 5-тонных. Сколько и каких автомобилей купить для обеспечения максимальной суммарной грузоподъемности автопарка».
Ответ
x1 = 15 x2 = 18
Fmax = 135
Для обеспечения максимальной суммарной грузоподъемности автопарка необходимо 15 автомобилей 3-х тонных и 18 автомобилей 5-ти тонных.
Решение
Обозначим количество 3-тонных автомобилей за x, а количество 5-ти тонных автомобилей за y.
Грузоподъёмность суммарная автопарка буде равна:
F(x1, x2) = 3x1+ 5x2 max
Ограничение по бюджету:
4x1+ 5x2 150
Ограничение по техобслуживанию:
- не более 20 единиц 3-тонных автомобилей сразу:
x1 20
- не более 18 единиц 5-тонных автомобилей:
x2 18
Введем ограничение по смыслу задачи:
- количество автомобилей целое и неотрицательное:
x1 0
x2 0
Необходимо найти количество и тип автомобилей по весу для обеспечения максимальной суммарной грузоподъемности автопарка.
Нахождение оптимального плана задачи линейного программирования
Найти наибольшее значение функции
F =
3 x1 + 5 x2
при следующих ограничениях:
4 x1 + 5 x2 ≤ 150
x1
≤ 20
x2 ≤ 18
x1 ≥ 0 x2 ≥ 0
1
. Свободные члены системы должны быть неотрицательными.
Данное условие выполнено.
2. Каждое ограничение системы должно представлять собой уравнение.
4 x1 + 5 x2 ≤ 150
x1
≤ 20
x2 ≤ 18
4 x1 + 5 x2 +
S1
= 150
x1
+
S2
= 20
x2
+
S3 = 18
S1 ≥ 0, S2 ≥ 0, S3 ≥ 0.
Введенные переменные S1, S2, S3, называются балансовыми переменными.
3. Нахождение начального базиса и значения функции F, которое соответствует найденному начальному базису.
Приравниваем свободные переменные нулю, устно находим значения базисных переменных. Функция F выражена через свободные переменные, следовательно, ее значение для данного решения можно найти мгновенно.
x1 = 0 x2 = 0 S1 = 150 S2 = 20 S3 = 18 => F = 0
Начальный базис найден и получено значение функции F соответствующее найденному базису.
4