Методы оптимальных решений № 1. Задачи линейного программирования и

решения
Д.ф.-м.н. Михайлова М.В.

Владимир Борисович к.т.н..
Контакты: lvb_imes@mail.ru

– достигнуть наибольшего или наименьшего значения данной функции при определенных

ограничениях на переменные, от которых эта функция зависит.
Ограничения задаются в виде систем уравнений или неравенств, которые называются системами ограничений. Функция называется целевой функцией.
Решение экстремальной задачи – это набор значений неизвестных, удовлетворяющих системе ограничений, при котором данная функция достигает своего экстремума – оптимального решения.
Математическая дисциплина, занимающаяся изучением экстремальных задач и разработкой методов их решения, называется математическим программированием.

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

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

одну целевую функцию) часто встречаются задачи, заключающиеся в поиске оптимального

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

Стандартная ЗЛП имеет вид:



2) Каноническая ЗЛП имеет вид:



3) Общая ЗЛП

имеет вид:

Любую ЗЛП можно свести к каноническому виду:
1) если

, то ;
2) если , то ;
3) если , то ;
4) если переменная не имеет условия неотрицательности, то она представляется в виде разности двух неотрицательных переменных.

представим в виде

равенства путем добавления к левой части неотрицательной переменной u:
Неравенство представим в виде равенства путем вычитания из левой части неотрицательной переменной v:
Неравенство представим в виде равенства путем добавления к левой части неотрицательной переменной с:
Целевую функцию заменим на:
Так как на переменную х не наложено условие неотрицательности, то заменим ее разностью двух неотрицательных переменных a и b:

f=c1x+c2ymax(min) 2) в канонической форме n=m+2.
Строится на графике

область допустимых решений, определяемая системой ограничений и условиями неотрицательности, в результате возможны случаи:
ОДР – пустое множество, тогда задача не имеет решения;
ОДР – единственная точка, тогда оптимальное решение будет в этой точке.
ОДР – выпуклый многоугольник:
А) найти координаты всех угловых точек и вычислить значение целевой функции в этих точках. Наибольшее значение определяет максимум функции, а наименьшее значение – минимум. Если в двух соседних точках значение максимума (минимума) совпадает, это означает, что экстремум достигается на отрезке, соединяющем эти точки.
Б) построить радиус-вектор с координатами (с1,с2), он задает направление возрастания целевой функции. Строим мысленно перпендикуляр к этому вектору и параллельно будем его переносить вдоль заданного вектора. Та точка, через которую мы входи в ОДР будет содержать минимум функции, а та точка, через которую будем покидать ОДР содержит максимум функции. Определим координаты указанной точки и значение целевой функции в ней.
ОДР – это выпуклая неограниченная область, тогда экстремум может находиться либо в угловой точке, либо на отрезке, либо уходить в бесконечность, т.е. не существовать.

ограничений к виду

неравенства y≤3+x является прямая y=3+x, проходящая через точки (0;3) и

(3;6). Так как в этом неравенстве y меньше выражения, стоящего после знака равенства, то выбираем ту полуплоскость, которая расположена ниже прямой.
Границей второго неравенства y≥3-3x является прямая y=3-3x, проходящая через точки (0;3) и (3;-6). Так как в этом неравенстве y больше выражения, стоящего после знака равенства, то выбираем ту полуплоскость, которая расположена выше прямой.
Границей третьего неравенства x≤3 является прямая x=3, которая перпендикулярна оси OY. Так как x≤3, то выбираем левую полуплоскость.
Условия неотрицательности x≥0 и y≥0 ограничивают нашу область первой координатной четвертью.

области
из решения
систем уравнений:

что минимум достигается в точке B, следовательно, решение имеет вид:
при

x=3 и y=6 целевая функция достигает

имеет канонический вид, причем число переменных n=6, а число ограничений

m=4. Поэтому графический метод можно применить.

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



Подставим эти выражения в целевую функцию:

, получим




Из этих неравенств выразим переменную через

:

:
Границей первого ограничения

выступает прямая, проходящая через точки (0,2) и (5,4). Так как неравенство содержит знак ≤, то выбираем нижнюю полуплоскость.
Границей второго ограничения выступает прямая, проходящая через точки (1,0) и (5,4). Так как неравенство содержит знак ≥, то выбираем верхнюю полуплоскость.
Границей третьего ограничения выступает прямая, проходящая через точки (6,0) и (0,3). Так как неравенство содержит знак ≤, то выбираем нижнюю полуплоскость.
Границей четвертого ограничения выступает прямая, проходящая через точки (3,5) и (0,-5). Так как неравенство содержит знак ≥, то выбираем верхнюю полуплоскость.

целевой функции.
Для этого построим радиус-вектор с координатами (1;1), направление

которого показывает направление возрастания целевой функции .
Строим мысленно перпендикуляр к этому вектору и параллельно будем его переносить вдоль заданного вектора.
Та точка, через которую мы будем покидать ОДР, содержит максимум функции.
Это точка С. Найдем ее координаты.
Так как точка С лежит на пересечении
3-ей и 4-ой прямых, то решим
систему уравнений:

и

при ограничениях

равно …


А) 6
Б) 10
В) 14
Г) 16

максимальное значение
функции
равно …

А) 27
Б) 29
В) 20
Г) 31

при ограничениях

равно …



А) 8
Б) 10
В) 6
Г) 4

методов их решения, называется …


5. Задача вида

является …
канонической ЗЛП
общей ЗЛП
стандартной

ЗЛП
задачей нелинейного программирования

Множество всех планов задачи линейного программирования называется …
Допустимой областью
Критической областью
Оптимальным

решением
Решением задачи

Б)




В) Г)

(0;4)
Б) (3;4)
В) (6;0)
Г) в любой точке отрезка АВ

(0;4)
Б) (3;4)
В) (6;0)
Г) в любой точке отрезка АВ

решений систем неравенств:





3. Решить геометрически задачи: