Найти оптимальное решение задачи (точку минимума и точку максимума), математическая модель которой имеет вид:
Построим область допустимых решений, т.е. решим графически систему ограничений. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
1. Прямая 2х1 + 4х2 = 16;
х1
х2
0 4
4 2
2. Прямая -4х1 + 2х2 = 8;
х1
х2
0 4
1 6
3. Прямая х1 + 3х2 = 9;
х1
х2
0 3
3 2
4. Прямая 6х1 + 5х2 = 30;
х1
х2
0 6
5 0
Убедимся, что координаты точек, лежащих внутри отрезка АВ, удовлетворяют системе ограничений. Возьмем точку: х1 = 3, 6·3 + 5х2 = 30,
5х2 = 12, х2 = 2,4.
М(3;2,4).
; верно.
Таким образом, областью допустимых решений является отрезок АВ.
Строим вектор – вектор целевой функции задачи. Проводим через точку О(0;0) целевую прямую, перпендикулярную вектору : -2х1 – х2 = 0.
Для определения максимального значения осуществляем параллельный перенос полученной прямой в направлении вектора. Прямая выходит из области допустимых решений в точке В.
Точка В является точкой пересечения прямых 2х1 + 4х2 = 16 и 6х1+5х2 = 30. Найдем ее координаты:
; -7х2 = -18;
х2 =18/7≈ 2,57; х1 =20/7≈ 2,86.
Максимальное значение целевой функции:
.
Для определения минимального значения осуществляем параллельный перенос полученной прямой в направлении, противоположном направлению вектора. Прямая выходит из области допустимых решений в точке А.
Точка А является точкой пересечения прямых х1 + 3х2 = 9 и 6х1+5х2 = 30. Найдем ее координаты:
; -13х2 = -24;
х2 =24/13≈ 1,85; х1 =45/13≈ 3,46.
Минимальное значение целевой функции:
.
Вывод:
Минимальное значение целевой функции достигается при х1 =45/13≈ 3,46;
х2 =24/13≈ 1,85; ;
максимальное значение целевой функции достигается при х1 =20/7≈ 2,86;
х2 =18/7≈ 2,57; .
Задание №2
Нахождение опорных планов.
Найти двумя методами (методом северо-западного угла и методом минимального элемента) опорный план следующей транспортной задачи. Запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 125, 90, 130, 100 ед. продукции. Тарифы перевозки в рублях за единицу продукции следующие:
.
Нужно полное решение этой работы?
Решение
Поставщик Потребитель Запасы товаров
В1
В2
В3 В4
А1
5 8 1 2 210
А2
2 5 4 9 170
А3 9 2 3 1 65
Потребность 125 90 130 100
Проверим выполнение балансового условия:
;.
Поскольку потребности заказчиков и возможности поставщиков совпадают, транспортная задача является задачей закрытого типа.
1. Составляем опорный план методом северо-западного угла.
Поставщик Потребитель Запасы товаров
В1
В2
В3 В4
А1
5[125] 8[85] 1 2 210
А2
2 5[5] 4[130] 9[35] 170
А3 9 2 3 1[65] 65
Потребность 125 90 130 100
План начинает заполняться с верхнего левого угла. Потребителю В1 требуется 125 ед. товара. Удовлетворяем эти потребности из запасов поставщика А1. Тогда в первой строке остается распределить 210 – 125 = 85 единиц товара. Распределяем их потребителю В2. Запасы А1 закончились. Потребителю В2 осталось получить 90 – 85 = 5 ед. товара.
Переходим на вторую строку таблицы и распределяем запасы поставщика А2: 5 ед
. – потребителю В2, 130 ед. – потребителю В3 и 35 ед. – потребителю В4. Потребности В2 и В3 удовлетворены в полном объеме. Потребителю В4 требуется еще 100 – 35 = 65 ед. товара.
Переходим на третью строку таблицы и распределяем 65 ед. товара потребителю В4 из запасов поставщика А3.
Получаем первый опорный план, который является допустимым, так как все товары распределены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи:
При построении опорного плана число занятых клеток таблицы должно быть m + n - 1 = 6, где m =3 – число поставщиков, n = 4 – число потребителей. Поскольку это условие выполнено, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:F(x) = 5·125 + 8·85 + 5·5 + 4·130 + 9·35 + 1·65 = 2230.
2
Задать вопрос
на новый заказ в Автор24.
