Эксперт по сдаче вступительных испытаний в ВУЗах
Поставить задачу линейного программирования и найти оптимальное решение в ситуации: «Грузоперевозчик покупает автомобили. Бюджет покупки – 150 д.е. Цена 3-тонного автомобиля составляет 4 д.е., 5-тонного – 5 д.е. Возможности грузоперевозчика по техническому обслуживанию автомобилей – не более 20 единиц 3-тонных автомобилей сразу и не более 18 единиц 5-тонных.
Сколько и каких автомобилей купить для обеспечения максимальной суммарной грузоподъемности автопарка».
Решение
1) Составим экономико-математическую модель задачи.
Объектом моделирования является процесс получения максимальной суммарной грузоподъемности автопарка, а целью – оптимизация плана закупки автомобилей.
Задача относится к классу оптимизационных задач. Математическая модель для задач такого класса состоит в построении целевой функции, для которой надо найти экстремум, при ограничениях.
Для решения поставленной задачи введем обозначения:
х
1 – количество купленных 3-тонных автомобилей;
х
2 – количество купленных 5-тонных автомобилей.
Общую суммарную грузоподъемность автопарка можно определить по формуле:
Функция называется целевой, ее следует максимизировать. Поэтому получаем:
На целевую функцию накладываются следующие ограничения:
1) Бюджет покупки автомобилей составляет 150 д.е.:
2) Возможности грузоперевозчика по техническому обслуживанию автомобилей – не более 20 единиц 3-тонных автомобилей сразу и не более 18 единиц 5-тонных. Таким образом, накладываются следующие ограничения:
3) Количество купленных автомобилей не может быть отрицательным:
4) Условия целочисленности купленных автомобилей:
Математическая модель задачи: составить оптимальный план покупки автомобилей (х
1, х
2), обеспечивающий максимальную суммарную грузоподъемность:
при ограничениях:
Экономико-математическая модель задачи составлена.
2) Решим задачу графическим методом.
Построим множество допустимых решений или, что то же самое, область допустимых решений. Условия неотрицательности переменных х
1 ³ 0 и х
2 ³ 0 показывают, что область допустимых решений будет лежать в первом квадранте системы координат.
Построим каждую прямую и определим полуплоскости, заданные неравенствами (рис. 1).
Построим уравнение по двум точкам.
| |
x1 |
x2 |
| Первая точка |
0 |
30 |
| Вторая точка |
37,5 |
0 |
Теперь нужно выбрать одну из двух полуплоскостей, на которые прямая разделила плоскость, и заштриховать эту полуплоскость. Чтобы правильно выбрать, возьмем точку плоскости, не лежащую на прямой, и подставим ее в неравенство. Например, точка не лежит на прямой:
Неравенство верное, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.
Построим уравнение . Эта прямая проходит через точку x
1 = 20 параллельно оси 0х
2. Определим полуплоскость, задаваемую неравенством. Так как знак неравенства , то нас интересуют точки, лежащие левее построенной прямой.
Построим уравнение . Эта прямая проходит через точку x
2 = 18 параллельно оси 0х
1. Определим полуплоскость, задаваемую неравенством. Так как знак неравенства , то нас интересуют точки, лежащие ниже построенной прямой.
Рис. 1. Область допустимых решений
Обозначим границы области многоугольника решений. При анализе рис. 1 можем сделать вывод, что областью допустимых решений (ОДР) является пятиугольник с вершинами ABCDE.
Рассмотрим целевую функцию задачи:
Построим прямую, отвечающую значению функции :
Вектор-градиент = , составленный из коэффициентов целевой функции, указывает направление максимизации функции . Начало вектора – точка (0; 0), конец – точка (3; 5). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией (рис. 2).
Рис. 2. Прямая целевой функции на максимум
Прямая пересекает область в точке С. Так как точка С получена в результате пересечения прямых, заданных уравнениями и , то ее координаты удовлетворяют уравнениям этих прямых.
Решаем систему уравнений:
Решив систему уравнений, получили:
x
1 = 15; x
2 = 18.
Найдем максимальное значение целевой функции:
Ответ. ; . Для обеспечения максимальной суммарной грузоподъемности автопарка требуется купить 15 3-тонных и 18 5-тонных автомобилей. При использовании данного плана покупки автомобилей суммарная грузоподъемность будет максимальной и составит 135 тонн.
