Балашовский филиал

Шаг 2. Строим вектор (5,2; –1).
Шаг 3. Проводим линию уровня L₀ таким образом, чтобы она имела
с ОДР общие точки.
Шаг 4—5. Перемещаем L₀ по направлению вектора до линии уровня, которая являлась бы границей полуплоскости, целиком содержащей ОДР. Однако закончить указанное перемещение невозможно. Из Error: Reference source not found видно, что какую бы линию уровня в направлении вектора нормали ни провести (штрихованные прямые на чертеже), любая из них пересекает ОДР. Следовательно, L_max= +∞. Это означает, что задача на максимум неразрешима.
2
. Теперь найдем значения переменных, при которых целевая функция минимизируется. Шаги 1—3 точно те же, что и при решении максимизационной задачи.
Шаг 4. Перемещаем линию уровня L₀ в направлении, противоположном вектору , до линии, являющейся границей полуплоскости, целиком содержащей ОДР. Такой линией является прямая L₀^–, проходящая через точку В. Следовательно, L_min = L(B).
Шаг 5. Координаты точки В определяются как пересечение прямых 2x₁ + 5x₂ = 10 и –x₁ + x₂ = 1. Решая соответствующую систему уравнений, найдем координаты точки В: x₁=5/7 и x₂=12/7. Таким образом, L_min = 5,2 · 5/7 –
– 12/7 = 2.

3. Применение графического метода
при решении транспортной задачи

Дадим подробную иллюстративную характеристику схемы алгоритма применительно к конкретной транспортной задаче. Это позволит не приводить последующее ее формальное описание.
Пример 4. а) Найти значения переменных, при которых функция
L(X) = 4x₁₁ + 8x₁₂ + 9x₁₃ + 7x₂₁ + 3x₂₂ + 5x₂₃ принимает экстремальные значения при условии, что:
x₁₁ + x₁₂ + x₁₃ = 110,
x₂₁ + x₂₂ + x₂₃ = 100,
x₁₁ + x₂₁ = 60,
x₁₂ + x₂₂ = 80,
x₁₃ + x₂₃ = 70,
x₁₁ 0, x₁₂ 0, x₁₃ 0, x₂₁ 0, x₂₂ 0, x₂₃ 0.
б) Интерпретируя переменные и константы, входящие в указанные математические модели, в соответствии с вариантами примера 1 из § 1, дать экономическую характеристику полученных решений.
Решение. а) Введем новые переменные u₁, u₂, положив u₁ = x₁₁, u₂ = x₁₂, и выразим через них остальные. Получим x₁₃ = – u₁ – u₂ + 110, x₂₁ = – u₁ + 60, x₂₂ = – u₂ + 80, x₂₃ = 70 – x₁₃ = 70 – (– u₁ – u₂ + 110) = u₁ + u₂ – 40. Соответственно L(X) = L(U) = 4u₁ + 8u₂ + 9(– u₁–u₂ +110) + 7(– u₁ + 60) + 3(– u₂ + 80) +
+ 5(u₁ + u₂ – 40) = –7u₁ + u₂ + 1 450.
Тогда с учетом неотрицательности переменных x_ij для i, j= 1, 2, 3, формулировка исходной задачи приобретает следующий вид:
L(U) = –7u₁ + u₂ + 1 450 max (min)

u₁ 0, u₂ 0.
Для решения задачи с такой формулировкой применим графический метод. Введем на плоскости прямоугольную систему координат O_u1_u2
и построим ОДР данной задачи аналогично тому, как это было сделано
в примере 1. Ограничительные условия определяют на плоскости многоугольник ABDEFG (Error: Reference source not found), вершины которого имеют соответственно координаты: (0; 40), (0; 80), (30; 80), (60; 50), (60; 0), (40; 0). Строим вектор (–7; 1). Проводим линию уровня _L0. Она задается уравнением 7_u1 +
+ _u2 + 1 450=const. На Error: Reference source not found построена линия уровня, соответствующая значению 1 450. Сначала найдем значения переменных _u1, _u2, при которых целевая функция принимает минимальное значение. Поэтому перемещаем _L0 в направлении, противоположном вектору . Точкой выхода из ABDEFG является точка F. Следовательно, наименьшее значение функции L(U) на ОДР достигается при _u1 = 60, _u2 = 0. Поэтому _Lmin= –7·60 +
+ 0 + 1 450 = 1 030. Теперь найдем значения переменных _u1, _u2, при которых функция L(U) принимает максимальное значение. Перемещаем _L0 по направлению вектора . При таком перемещении точкой выхода из шестиугольника ABDEFG является точка B(0; 80). Следовательно, _Lmax= L(B) =
=
–7·0 + 80 + 1 450 = 1 530.
Т

аким образом,
L_min= 1 030 при x₁₁ = 60, x₁₂ = 0, x₁₃ = 50, x₂₁ = 0, x₂₂ = 80, x₂₃ = 20;
L_max= 1 530 при x₁₁ = 0, x₁₂ = 80, x₁₃ = 30, x₂₁ = 60, x₂₂ = 0, x₂₃ = 40.
б) Сначала рассмотрим случай, когда в качестве критерия экономической эффективности выступает минимум указанной величины.
Полученный в п.(а) ответ соответствует для варианта 1 оптимальному плану перевозок. Запишем его в виде матрицы
_опт = ,
экономическая интерпретация которой, благодаря Рис. 1, весьма прозрачна. При таком плане перевозок затраты будут минимальны, а именно 1 030.
Теперь рассмотрим случай, когда в качестве критерия экономической эффективности выступает максимум указанной величины:
Полученный в подпункте а ответ соответствует для варианта 2 оптимальному плану временнóй загрузки станков по выполнению каждой операции. Его также (как и для варианта 1) удобно записать в виде матрицы
_опт = .
Экономическая интерпретация полученной матрицы такова:

• 
  на первом станке имеет смысл выполнять вторую и третью операции продолжительностью 80 и 30 часов соответственно;
  
• 
  на втором — первую и третью операции продолжительностью 60
  и 40 часов соответственно.
  

При таком плане будет обработано наибольшее количество деталей,
а именно 1 530.
Отметим одну немаловажную деталь. Иногда ЛПР, наряду с оптимальным планом, интересует такой план временнóй загрузки станков, при котором будет обрабатываться наименьшее количество деталей. Как правило, это происходит в том случае, когда по тем или иным причинам осуществить оптимальный план не удается. Поэтому приходится варьировать временнýю загрузку станков и, естественно, при этом нужно постараться исключить такой вариант, при котором будет обрабатываться наименьшее количество деталей. Для данной задачи таким вариантом является план, матрица которого имеет следующий вид:
.
При указанной временнóй загрузке станков будет обработано минимальное количество деталей, а именно, 1 030 (разница с оптимальным планом в 500(!) деталей). (Проведите аналогичное исследование для варианта 1, а именно, укажите такой план перевозок, при котором транспортные расходы будут наибольшими.)