Задача 1
Решить графическим методом типовую задачу оптимизации.
Совхоз для кормления животных использует два вида корма. В дневном рационе должно содержаться не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В.
Какое количество корма надо расходовать ежедневно на одно животное, чтобы затраты были минимальными? Использовать данные таблицы.
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум, и почему?
Решение.
1)Построение экономико-математической модели задачи
Введем переменные : X1- количество корма 1, X2 - количество корма 2 (в кг).
Целевая функция в данном случае затраты на корма обоих видов. Требуется найти такое распределение кормов обоих видов, чтобы суммарные затраты на покупку кормов были минимальны. При этом значения переменных должны находиться в области допустимых решений.
Целевая функция задачи :
f(x) = 0,2X1 + 0,3Х2
Найдём минимум целевой функции.
Область допустимых решений (ОДР) задачи, согласно условию:
2X1 + Х2 ?6
X?0 Х2?0
2X1 + 4Х2?12
2) Построим область допустимых решений (ОДР) задачи.
Условия неотрицательности переменных означают, что область решений будет лежат в первой четверти Декартовой системы координат.
Функциональные ограничения (неравенства) определяют область, являющуюся пересечением нижних полуплоскостей с граничными прямыми и осями координат :
2X1 + Х2 = 6
2X1 + 4Х2 = 12
Пересечение указанных полуплоскостей в первой четверти представляет собой область АВС (заштрихованная область для всех ограничений задачи ОДР).
3) Для определения направления движения к оптимуму построим вектор-градиент, соединив его вершину с началом координат О (0, 0). Строим градиент функции - вектор, показывающий направление возрастания функции f(x).
С=grad(f)= (?f/?x1; ?f/?x2) = ( 0,2; 0,3)
4) Построим некоторую линию уровня .
Пусть, например, а = 0. На эскизе такой линии уровня отвечает прямая ОХ, перпендикулярная вектор-градиенту.
0,2 X1+ 0,3 X2 = 0
5) При максимизации целевой функции (ЦФ) необходимо перемещать линию уровня ОХ в направлении вектор - градиента, а при минимизации - в противоположном направлении. Предельной точкой при таком движении линии уровня ОХ является точка В - крайняя точка (вершина) ОДР (по - другому называемой многоугольником планов). Далее она (линия уровня) уже не пересекает единственную точку ОДР (так как область неограниченна сверху).
6)Определим координаты точки В, являющейся точкой пересечения граничных прямых , решив систему уравнений :
2*X1+ Х2=6
2*X1 + 4*Х2 = 12
Точка 0( 0; 0 ) - точка начала координат.
Получаем точку В (2; 2) - вершину многоугольника (сектора) планов.
7) Точка В является так называемым оптимальным планом. В точке В целевая функция принимает свое минимальное значение при заданной системе ограничений. Эта точка отвечает минимально возможным затратам на корма при заданной ОДР. При заданной ОДР отсутствует точка максимума для целевой функции Смысл данного факта: затраты на корма при данной ОДР никак не ограничиваются (хотя в реальных случаях такая ситуация невозможна). Таким образом, целевая функция в задаче линейного программирования принимает, при заданной системе ограничений :
минимальное значение-min(f)=f(В)=0,2*2 + 0,3 *2 = 1. (тыс. руб).
максимальное значение - отсутствует (функция неограниченна сверху на ОДР). С помощью надстройки ЕХСЕL «Поиск решения" минимум целевой функции, также как и при использовании графического метода. Максимум найти не удается (сообщается, что результат не сходится); в таблице помещено только одно из возможных значений.
Ответ: максимального значения - нет (ОДР неограничен сверху);
min( x) = (2; 2); min(f)= 1 (тысяч денежных единиц).
Графическое решение