2. Задача составления рациона.
Имеется два вида корма: I и II, которые содержат питательные вещества . Содержание единиц питательных веществ в одном килограмме корма и необходимый минимум питательных веществ приведены в таблице 2.
Таблица 2
Питательное вещество |
Необходимый минимум питательных веществ |
Число единиц питательных веществ в одном килограмме корма |
|
I |
II |
||
|
|
|
|
|
|
|
|
|
|
|
|
Стоимость килограмма корма I составляет 4 руб., II – 6 руб.
Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.
Решение:
Тогда этот рацион будет включать в себя вещества:
При этом содержание питательных веществ в рационе должно быть не ниже установленного предела т.е.:
По смыслу задачи переменные и должны быть неотрицательные, т.е.
,
.
Общая
стоимость рациона составит: 
Обобщим задачу составления рациона. Для этого обозначим:
– виды кормов;
– виды питательных веществ;
– количество килограммов корма в дневном рационе;
– необходимый минимум содержания в рационе питательного вещества ;
– стоимость единицы корма .
Тогда экономико-математическая модель задачи примет вид:
Найти такой рацион X=(x1,x2,…,xn), удовлетворяющий системе
и условию
при котором функция принимает минимальное значение.
Графический (геометрический) метод решения задач линейного программирования
Графическим методом решается следующая стандартная задача линейного программирования:
Этапы графического метода:
Этап 1. Построение прямых, ограничивающих область допустимых решений (ОДР).
Для этого в системе ограничений (2) и условии неотрицательности (3) меняем знаки неравенства на знаки равенства, и строим эти прямые в координатной плоскости.
Пример
Меняем знаки неравенства на знак равенства:
Для построения каждой прямой найдем две ее любых точки:
а)
б)
в)
По найденным координатам строим следующие прямые:
Этап 2. Определение решения для каждого из неравенств системы ограничений.
Каждая из построенных прямых делит плоскость на две полуплоскости, одна из которых содержит решение, а вторая – не содержит решения.
Полуплоскость, удовлетворяющую ограничению по каждой прямой, ищут следующим образом: берут произвольную точку на координатной плоскости (например, точку О с координатами (0;0)) и координаты этой точки подставляют в соответствующее неравенство из системы ограничений (2):
Продолжаем рассматривать наш пример:
а)
Рассмотрим неравенство 
Возьмем
координаты произвольной точки О
(например, (0;0)) и подставим их вместо 
и 
в неравенство. Получим: 
- справедливое неравенство.
Теперь посмотрим на рисунок:
Красная прямая делит плоскость на две полуплоскости, и только одна из них содержит решение.
Поскольку в результате подстановки координат (0;0) было получено справедливое неравенство, то та полуплоскость, которая содержит точку О с данными координатами, будет содержать решение. Зафиксируем это на рисунке стрелочками.
б)
Рассмотри неравенство 
Возьмем
координаты произвольной точки О (0;0) и
подставим их вместо
в неравенство. Получим: 
- несправедливое неравенство.
Теперь посмотрим на рисунок. Поскольку неравенство несправедливое, то содержать решение будет та полуплоскость, которая не содержит точку О. Отметим это на рисунке.
в)
по неравенству 
– аналогичные действия.
В итоге, совместив все три решения в одной координатной плоскости, получим:
Этап 3. Нахождение области допустимых решений (ОДР).
ОДР – это фигура на плоскости, образованная пересечением полуплоскостей, в которых каждое ограничение-неравенство имеет решения.
Областью допустимых решений может быть:
а) выпуклая многоугольная область;
б) точка;
в) пустое множество (в нем нет решений);
г) выпуклый многоугольник.
В нашем примере:
Областью допустимых решений будет область АВСD.
Этап
4. Построение вектора-градиента 
.
Начало координат (т.е. точка О (0;0)) является начальной точкой вектора-градиента.
Для определения второй точки вектора-градиента находят производные прямой целевой функции по каждой переменной по формулам:
– координата
по оси 
– координата
по оси 
Вектор-градиент указывает направление максимизации целевой функции . Направление, обратное вектору-градиенту, соответствует направлению минимизации целевой функции.
Возможны следующие направления максимизации целевой функции :
а)
|
б)
|
в)
|
г)
|
В нашем примере:
– координата
по оси
,
т.е. это коэффициент при
в F(x);;
– координата
по оси
,
т.е. это коэффициент при
в F(x).
Построим вектор градиент. Начальная точка имеет координаты (0;0), вторая точка – (1;1).
Примечание:
Этап 5. Построение прямой целевой функции.
Приравниваем прямую целевой функции к нулю и строим ее.
В нашем примере:
Этап 6. Определение точек оптимума (максимума или минимума) целевой функции.
Движением прямой параллельно самой себе в направлении вектора-градиента находят точки, в которых целевая функция принимает оптимальное значение, либо устанавливают ее неограниченность сверху (снизу). Рассмотрим некоторые возможные случаи:
а) |
б) |
в) |
г) |
д) максимума нет, т.к. ОДР сверху не ограничена |
е) минимума нет, т.к. ОДР снизу не ограничена |
ж) прямая F(x) и отрезок ВС параллельны. Здесь F(x) будет иметь бесконечное множество максимальных решений на отрезке ВС. Такая ситуация может иметь место, если коэффициенты при x1 и x2 в функции F(x) и одном из неравенств кратные. |
|
В нашем примере:
Самой первой точкой из области допустимых решений, лежащей на пути движения прямой целевой функции F(x), перемещаемой в направлении вектора-градиента параллельно самой себе, является точка А, следовательно, данная точка является точкой минимума.
Самая последняя точка из ОДР, лежащая на пути движения прямой целевой функции F(x) в направлении вектора-градиента, будет точкой максимума. Поскольку в нашем примере коэффициенты при переменных в целевой функции F((x) и ограничения-неравенства совпадают, то прямая целевой функции параллельна прямой . Это значит, что целевая функция будет иметь максимальные значения на всем протяжении отрезка CD.
Этап 7. Определение координат точек максимума и минимума.
Для этого уравнения прямых, пересечением которых образована данная точка максимума или минимума, заключают в систему и решают.
В нашем примере:
а) Нахождение координат минимума:
т. Аmin:
б) Нахождение координат т. Сmax;
в) Нахождение координат т. Dmax;
Этап 8. Нахождение максимального и минимального значения целевой функции
Для этого найденные координаты точек максимума или минимума подставляют в уравнение целевой функции F(x).
В нашем примере:
Ответ:
максимальное
значение целевой функции 
и достигается в любой из точек отрезка
CD;
частными решениями являются т. С (4,1;
4,9) и т. D (9;0);
минимальное
значение целевой функции
и достигается в т. А (2; 0).