- •Лекция 1. Математическое программирование. Понятие об оптимизационных задачах. Задача линейного программирования (злп). Графический метод решения злп. Симплекс-метод решения злп.
- •4. Графический метод решения злп. Основные свойства злп.
- •5. Стандартная форма злп, правила построения.
- •1) Все переменные неотрицательны;
- •2) Все ограничения заданы в виде уравнений;
- •3) Целевая функция сформулирована на минимум.
- •6. Канонический вид злп, начальное допустимое базисное решение (ндбр),
- •7. Симплекс-метод.
4. Графический метод решения злп. Основные свойства злп.
Графический метод решения ЗЛП используется, если число неизвестных задачи не больше 2 или если разность между числом неизвестных и ограничений задачи, записанных в виде уравнений не более двух.
Схема решения.
Строим область допустимых решений.
Строим линию уровня.
Определяем направление градиента.
Определяем точку максимума (минимума):
Точка максимума – точка допустимой области, наиболее удаленная от линии уровня в направлении градиента, точка минимума - точка допустимой области, наиболее удаленная от линии уровня в направлении антиградиента.
При решении ЗЛП возможны следующие случаи:
Основные свойства ЗЛП (см. рис.).
ЗЛП является выпуклой задачей, поэтому решение всегда единственно.
Оптимальное решение достигается по крайней мере в одной из вершин допустимой области: а) только в одной вершине; б) в двух вершинах и имеет бесконечное множество планов.
Если допустимая область не ограничена, то ЗЛП может быть разрешима или не разрешима, что зависит от целевой функции: в) задача на maxне разрешима, а наmin– разрешима; г) ЗЛП не разрешима.
Если допустимая область состоит из единственной точки, то в ней достигается и максимум и минимум – д).
Если допустимая область пуста, то ЗЛП не разрешима – е).
Если допустимая область ограничена и не пуста, то ЗЛП всегда имеет решение.
5. Стандартная форма злп, правила построения.
Графический метод решения ЗЛП можно использовать, если число неизвестных равно 2 или разность между числом неизвестных и числом ограничений, записанных в виде уравнений, равна 2. В общем случае эти требования не всегда выполняются. Чтобы использовать для решения некий универсальный метод решения, ЗЛП необходимо записать в определенной, стандартной форме.
Стандартная форма ЗЛП представляет собой такой вид задачи, в котором:
1) Все переменные неотрицательны;
2) Все ограничения заданы в виде уравнений;
3) Целевая функция сформулирована на минимум.
Требования эти оправданы. Во-первых, поиск максимума линейной функции сводится к поиску минимума функции с противоположными по знаку коэффициентами: оптимальные точки совпадают, а значения целевых функций равны по абсолютному значению. Во-вторых, линейная функция не имеет экстремумов и достигает своего наибольшего или наименьшего значения на границе допустимой области, поэтому и решать необходимо не неравенства, а уравнения. Запишем правила приведения любой ЗЛП к стандартному виду.
Правила построения стандартной формы ЗЛП:
1) Если F(x) =C1x1+C2x2+ … +Cnxn max, то можно искать
F(x) = -C1x1–C2x2- … -Cnxn min.
2) Ограничения в виде неравенств () могут быть сведены к уравнениям введением дополнительных, уравновешивающих неотрицательных уравнений.
Например: 2х1+ 3х242х1+ 3х2+ х3= 4, х3- уравновешивающая переменная.
4x1+ 2x2 54x1+ 2x2–x4= 5,x4- уравновешивающая переменная.
3) Если некоторая переменная х может быть не ограничена знаком, то в стандартном виде такую переменную можно представить в виде разности двух неотрицательных переменных: x = x' – x'', x' , x''.
При этом дополнительные переменные не входят в целевую функцию. Стандартная форма ЗЛП в матричном виде выглядит так: Ax=b,x, F(x) =CTx min.