3. Задание целевой функции.

Критерием оптимизации являются денежные затраты, а целью – составление такого рациона, который обеспечивает минимум затрат. Суммарные затраты определяются ценой и количеством корма каждого вида в суточном рационе

.

Совокупность целевой функции и ограничений на переменные представляет собой математическую модель экстремальной экономической задачи.

Данная задача также обобщается на случай рациона, содержащего видов питательных веществ в количестве не менее единиц при использовании видов кормов.

Пусть - количество единиц -го питательного вещества, содержащегося в единице -го корма; - стоимость единицы -го корма, - количество единиц -го корма в суточном рационе.

Необходимо найти минимальное значение целевой функции (затрат)

(11)

при следующих ограничениях

. (12)

4. Графический метод решения задачи линейного программирования

Графический метод является наиболее простым и наглядным методом решения задач линейного программирования. Он применяется для решения задач с двумя переменными и ограничениями в виде неравенств, либо для решения канонических задач с переменными, при условии, что количество свободных переменных не больше двух, то есть, , где - ранг системы уравнений (6), которые задают ограничения задачи.

4.1. Геометрическая интерпретация задачи линейного программирования

В основу графического метода положена геометрическая интерпретация задачи линейного программирования с двумя переменными

, (13)

(14)

. (15)

Каждое ограничение (14) геометрически представляет собой одну из двух полуплоскостей, на которые прямая , соответствующая данному неравенству, делит всю координатную плоскость. Для того чтобы определить, какая из двух координатных полуплоскостей является областью решений неравенства, достаточно подставить в него координаты какой-либо точки, не лежащей на прямой. Если прямая не проходит через начало координат, то удобнее всего подставить точку с координатами . Если неравенство удовлетворяется, то областью решений является полуплоскость, содержащая данную точку. В противном случае областью решений будет полуплоскость, не содержащая данную точку.

Область допустимых решений (ОДР) задачи или многоугольник решений представляет собой общую часть плоскости, образованную пересечением всех полуплоскостей, соответствующих областям решений каждого из ограничений (14) и (15) задачи. Координаты точек этой области удовлетворяют всем ограничениям задачи.

Условия (15) неотрицательности переменных означают, что область допустимых решений задачи расположена в первой четверти координатной плоскости .

В зависимости от конкретной системы ограничений, область допустимых решений может быть точкой, отрезком, лучом, ограниченным выпуклым многоугольником или неограниченной многоугольной областью.

Для нахождения оптимального решения (оптимального плана) необходимо в области допустимых решений найти такую точку (или множество точек), в которой целевая функция достигает своего экстремального значения:

Для этого используют линии уровня целевой функции и опорные прямые.

Определение. Линией уровня целевой функцииназывается прямая, на которой целевая функция принимает постоянной значение

где .

Определение. Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений (многоугольником решений) и по отношению к которой эта область находится в одной из полуплоскостей.

Придавая параметру различные значения, получим семейство параллельных прямых - линий уровня, на которых целевая функция постоянна и равна значению этого параметра. При получим так называемую нулевую линию уровня, проходящую через начало координат

.

Из курса высшей математики известно, что вектор-градиент целевой функции

направлен по нормали к линиям уровня и определяет направление наискорейшего возрастания целевой функции. Координатами нормали к линии уровня являются коэффициенты целевой функции

.

Значения целевой функции возрастают при перемещении линии уровня в направлении нормали (при увеличении параметра ), и убывают – при перемещении в противоположном направлении.

Геометрически решение задачи линейного программирования (13)-(15) заключается в следующем.

Найти такую точку области допустимых решений, через которую проходит опорная прямая, на которой целевая функция достигает своего оптимального (максимального или минимального) значения.

При решении задач графическим способом могут встретиться следующие случаи.

1. Задача имеет единственное решение , когда целевая функция достигает своего экстремального значения в вершинах замкнутого выпуклого многоугольника (рис.1,а) или незамкнутой выпуклой многоугольной области допустимых решений (рис.1,б - целевая функция ограничена снизу и не ограничена сверху).

2. Задача имеет бесконечное множество решений, когда целевая функция достигает своего экстремального значения на одной из сторон многоугольника решений (рис.2,а,б). Оптимальное решение достигается не в одной точке, а на всем отрезке, каждая точка которого является оптимальной. В этом случае угол наклона опорной прямой совпадает с углом наклона прямой соответствующего ограничения. Такое решение называется альтернативным.

Общее решение в альтернативной задаче представляет собой выпуклую линейную комбинацию оптимальных решений и на концах отрезка:

. (16)

3. Задача не имеет оптимальных решений. В этом случае либо область допустимых решений пустая (рис.3,а) и система ограничений задачи несовместная, либо область незамкнута в направлении поиска экстремума целевой функции (рис.3,б).

ОДР

ОДР

Опорная Опорная

прямая прямая

а) б)

Рис. 1. Единственное оптимальное решение или при замкнутой ОДР (а);

единственное решение и отсутствие решения (задача максимизации) при незамкнутой ОДР (б)

ОДР ОДР

а) б)

Рис. 2. Бесконечное множество решений и при замкнутой ОДР (а); бесконечное множество решений и отсутствие решения при незамкнутой снизу ОДР (б)

а) б)

Рис. 3. Задача не имеет оптимальных решений при пустой (а) и незамкнутой (б) ОДР