02.14.2023

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

1. Постановка задачи линейного программирования
2. Условия применения графического метода
3. Алгоритм метода на примере решения задачи

К матемтическим задачам линейного программирования относят:
- исследование конкретных производственно-хозяйственных ситуаций, которые интерпретируются как задачи об оптимальном использовании ограниченных ресурсов

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

Классы ЛП относят к экстремальным задачам (задачи функции экстремума)

Экономико-математическая модель любой задачи ЛП включает
- целевую функцию - оптимальное значение, которое нужно отыскать
- ограничения в вие системы линейных уравнений и неравенств
- условия неотрицательности переменных
$F = c_{1}x_{1} + c_{2}x_{2} + \dots + c_{n}x_{n} \to max(min)$
F - целевая функция - математическое выражение критерия оптимальности

$F=\sum c_{i}x_{j} \to max(min)$
где F - критерий оптимальности (показатель характеризующий эффективность системы);
$x_{1}, x_{2}, x_{n}$ - переменные величины, обозначающие параметры системы и характеризующие её состояние
$n$ - число переменных
$c_{1}, c_{2}, c_{n}$ - коэффициенты при переменных

*Поиск результатов происходит в постоянно изменяющихся условиях. *

Система ограничений - совокупность математических выражений, описывающих свойства, взаимосвязи, закономерности и соотношения объекта.

$a_{11}x_{11}+\dots a_{1j}x_{j}+\dots a_{1n}x_{n}\geq,\leq b_{1}$
...
$a_{i_{1}}x_{1}+a_{ij}x_{j}+\dots+a_{in}\geq,\leq b_{1}$
...
$\sum_{ij}x_{j}\{=\}b_{i}, i=1,2,\dots m$
где $m$ - число ограничений
$b$ - коэффициенты переменных при ограничениях

Математическая модель задачи линейного программирования:
$F=c_{1}x_{1}+c_{2}x_{2}+\dots c_{n}x_{n} \to max(min)$

$x_{j}.+$

Задача: Найти такие неотрицательные значения переменных $x_{1}$, $x_{2}$ $x_{n}$, которые удовлетворяют ограничениям задачи и обращают в максимум или минимум функцию цели

Условия применения: если целевая функция в задаче ЛП зависит от двух переменных, то данная задача может быть решена графическим методом.

Задача: построить математическую модель задачи ЛП и решить задачу графическим методом.

При этом нужно определить площадь култур при возделывании
Сначала нужно представить математическую модель. Определяем то, что обозначаем за переменную.
Пусть $x_1$ - площадь кукурузы, а $x_{2}$ - площадь пшеницы. Тогда можем составить систему ограничений.
$x_{1}+x_{2}\leq 140$ - первое ограничение.
$x_{1}\geq 14$, т.е. более 10% от 140

Далее ограничение по ресурсам
(ищем оптимум в условиях ограниченности ресурсов)
$0,5x_{1}+0.25x_{1}\leq 65$
$2x_{1}+2.5x_{2}\leq 320$

В качестве целевой функции:
$80x_{1}+120x_{2}=max$

Строим график. Нужно найти область допустимых решений.
Необходимо неравенство превратить в уравнение.

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

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

Теперь нужно определить, какая именно точка будет являться оптимальной

... и вектор-градиент, который указывает направление движения линии уровня.

Линия уровня - прировняем целевую функцию к постоянной величине $a$.

Меняя значение $a$ получим семейство параллельных прямых, каждое из которых называется линией уровня.

Пусть $a=0$. Вычислим координаты двух точек, удовлетворяющих уравнению : $80x_{1}+120x_{2}=0$

В качестве одной из точек удобно взять начало координат. Т.е. точку с координатами 0,0.

Вектор-градиент - вектор, указывающий движению линию уровня.

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

Значение целевой функции (значние F(x)) на отдельной получаемой точке является максимальным.

В случае минимазации F(x) линию уровня надо двигать в направлении противоположном вектору-градиенту.