Д.ф.-м.н. Михайлова М.В.
МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ ТЕМА № 1 Линейное программирование (лекция) Преподаватель: Ларионов Владимир Борисович к.т.н.. Контакты: lvb_imes @mail.ru Автономная некоммерческая организация высшего образования ИНСТИТУТ МЕЖДУНАРОДНЫХ ЭКОНОМИЧЕСКИХ СВЯЗЕЙ INSTITUTE OF INTERNATIONAL ECONOMIC RELATIONS
Экстремальными называются задачи, в которых ставится цель – достигнуть наибольшего или наименьшего значения данной функции при определенных ограничениях на переменные, от которых эта функция зависит. Ограничения задаются в виде систем уравнений или неравенств, которые называются системами ограничений. Функция называется целевой функцией. Решение экстремальной задачи – это набор значений неизвестных, удовлетворяющих системе ограничений, при котором данная функция достигает своего экстремума – оптимального решения. Математическая дисциплина, занимающаяся изучением экстремальных задач и разработкой методов их решения, называется математическим программированием.
Различают: Линейное программирование, в котором и система ограничений и целевая функция линейны. Нелинейное программирование ( квадратическое, дробно-линейное и др.). П араметрическое программирование, в котором исходные данные зависят от некоторого параметра. Ц елочисленное программирование, в котором переменные являются целыми числами. В ыпуклое программирование, в котором ищется максимум вогнутой функции на выпуклом множестве. С тохастическое программирование, в котором либо целевая функция, либо ограничения содержат случайные величины. Д инамическое программирование, которое учитывает фактор времени. И другие виды.
Наряду с приведенными выше однокритериальными задачами (имеющими одну целевую функцию) часто встречаются задачи, заключающиеся в поиске оптимального решения при наличии несводимых друг к другу критериев оптимальности (несколько целевых функций). Например, принятие решения о строительстве дороги в объезд города должно учитывать такие факторы, как: выигрыш города в целом по соображениям экологии, проигрыш отдельных предприятий и фирм и многие другие. Если такие задачи решаются методами математического программирования, то говорят о задачах многокритериальной оптимизации. Эти задачи могут носить как линейный, так и нелинейный характер.
Различают три основные формы ЗЛП: 1) Стандартная ЗЛП имеет вид : 2) Каноническая ЗЛП имеет вид: 3) Общая ЗЛП имеет вид:
Теорема. Все эти задачи эквивалентны. Замечание: Любую ЗЛП можно свести к каноническому виду: 1) е сли, то ; 2) если, то ; 3) если, то ; 4) если переменная не имеет условия неотрицательности, то она представляется в виде разности двух неотрицательных переменных.
Привести задачу линейного программирования к каноническому виду. РЕШЕНИЕ. Неравенство представим в виде равенства путем добавления к левой части неотрицательной переменной u : Неравенство представим в виде равенства путем вычитания из левой части неотрицательной переменной v : Неравенство представим в виде равенства путем добавления к левой части неотрицательной переменной с: Целевую функцию заменим на: Так как на переменную х не наложено условие неотрицательности, то заменим ее разностью двух неотрицательных переменных a и b :
Получим каноническую задачу линейного программирования:
Графический способ применим, если: 1) n =2, f=c 1 x+c 2 y max(min) 2) в канонической форме n = m +2. Строится на графике область допустимых решений, определяемая системой ограничений и условиями неотрицательности, в результате возможны случаи: ОДР – пустое множество, тогда задача не имеет решения; ОДР – единственная точка, тогда оптимальное решение будет в этой точке. ОДР – выпуклый многоугольник: А) найти координаты всех угловых точек и вычислить значение целевой функции в этих точках. Наибольшее значение определяет максимум функции, а наименьшее значение – минимум. Если в двух соседних точках значение максимума (минимума) совпадает, это означает, что экстремум достигается на отрезке, соединяющем эти точки. Б) построить радиус-вектор с координатами (с 1,с 2 ), он задает направление возрастания целевой функции. Строим мысленно перпендикуляр к этому вектору и параллельно будем его переносить вдоль заданного вектора. Та точка, через которую мы входи в ОДР будет содержать минимум функции, а та точка, через которую будем покидать ОДР содержит максимум функции. Определим координаты указанной точки и значение целевой функции в ней. ОДР – это выпуклая неограниченная область, тогда экстремум может находиться либо в угловой точке, либо на отрезке, либо уходить в бесконечность, т.е. не существовать.
Найти графическим методом решение задачи линейного программирования РЕШЕНИЕ. Преобразуем систему ограничений к виду
Построим соответствующую область на плоскости OXY : Границей первого неравенства 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 ограничивают нашу область первой координатной четвертью.
Таким образом, получили область ABCD: Найдем координаты вершин этой области из решения систем уравнений:
Решим системы:
Вычислим значения целевой функции f=2x-3y в вершинах области: f(A)=2∙0-3∙3=-9, f(B)=2∙3-3∙6=6-18=-12, f(C)=2∙3-3∙0=6, f(D)=2∙1-3∙0=2. Очевидно, что минимум достигается в точке B, следовательно, решение имеет вид: при x=3 и y=6 целевая функция достигает
Решить графическим способом ЗЛП, имеющую более 2-х переменных: Эта задача имеет канонический вид, причем число переменных n=6, а число ограничений m=4. Поэтому графический метод можно применить.
РЕШЕНИЕ. Очевидно, что в качестве базисных переменных будут (они входят каждое только в одно уравнение системы ограничений), тогда переменные и будут свободными. Выразим базисные переменные через свободные: Подставим эти выражения в целевую функцию:
Так как все переменные, получим Из этих неравенств выразим переменную через :
Построим ОДР для этих ограничений на плоскости : Границей первого ограничения выступает прямая, проходящая через точки (0,2) и (5,4). Так как неравенство содержит знак ≤, то выбираем нижнюю полуплоскость. Границей второго ограничения выступает прямая, проходящая через точки (1,0) и (5,4). Так как неравенство содержит знак ≥, то выбираем верхнюю полуплоскость. Границей третьего ограничения выступает прямая, проходящая через точки (6,0) и (0,3). Так как неравенство содержит знак ≤, то выбираем нижнюю полуплоскость. Границей четвертого ограничения выступает прямая, проходящая через точки (3,5) и (0,-5). Так как неравенство содержит знак ≥, то выбираем верхнюю полуплоскость.
Таким образом, получили область ABCD ЕО :
Найдем вершину этого многоугольника, в которой достигается максимум целевой функции. Для этого построим радиус-вектор с координатами (1;1), направление которого показывает направление возрастания целевой функции. Строим мысленно перпендикуляр к этому вектору и параллельно будем его переносить вдоль заданного вектора. Та точка, через которую мы будем покидать ОДР, содержит максимум функции. Это точка С. Найдем ее координаты. Так как точка С лежит на пересечении 3-ей и 4-ой прямых, то решим систему уравнений:
В результате и
1. Максимальное значение целевой функции при ограничениях равно … А) 6 Б) 10 В) 14 Г) 16
2. Область допустимых решений задачи линейного программирования имеет вид: Тогда максимальное значение функции равно … А) 27 Б) 29 В) 20 Г) 31
3. Минимальное значение целевой функции при ограничениях равно … А) 8 Б) 10 В) 6 Г) 4
4. Математическая дисциплина, занимающаяся изучением экстремальных задач и разработкой методов их решения, называется … 5. Задача вида я вляется … к анонической ЗЛП о бщей ЗЛП с тандартной ЗЛП з адачей нелинейного программирования
6. Задача вида является … канонической ЗЛП общей ЗЛП стандартной ЗЛП задачей нелинейного программирования 7. Множество всех планов задачи линейного программирования называется … Допустимой областью Критической областью Оптимальным решением Решением задачи
8. Выберите полуплоскость, определяемую неравенством А) Б) В) Г)
9. В какой точке выделенного многоугольника достигается экстремум А) (0;4) Б) (3;4) В) (6;0) Г) в любой точке отрезка АВ
10. В какой точке выделенного многоугольника достигается экстремум А) (0;4) Б) (3;4) В) (6;0) Г) в любой точке отрезка АВ
1. Построить множество решений неравенств: 2. Построить множество решений систем неравенств: 3. Решить геометрически задачи:
