Решение задачи линейного программирования графическим методом - как проиллюстрировать в Mathcad?
Теория приведена, например, здесь (лекция 3). Отметим, что простейшим графическим методом решается задача только для двух неизвестных с линейной целевой функцией. Но рисовать на бумаге, что вышло, мне лично было бы лень.
Можно сделать похитрее и поавтоматизированней, чем в примере, например, попытаться автоматически штриховать область допустимых решений (ОДР), но не будем усложнять простую вещь.
Вот каким алгоритмом сделать понятнее всего. Возьмём классическую задачу линейного программирования (ЛП):
постановка задачи
Ограничения на неотрицательность x1, x2 тривиальны, а остальные определим как функции 2 переменных r1, r2, r3. Для построения графиков прямых, соответствующих этим трём ограничениям, решим их относительно переменной x2 как равенства, получатся функции f1(x1), ..., f3(x1):
представление ограничений задачи ЛП как уравнений прямых в Mathcad
Целевую функцию зададим как z(x1,x2), определим для неё 2 любых различных тестовых значения, Level1 и Level2. Они понадобятся, чтобы увидеть на графике направление возрастания функции (вектор градиента, перпендикулярный обеим линиям и направленный от z(x1,x2)=Level1 к z(x1,x2)=Level2):
определение целевой функции для задачи ЛП в Mathcad
Чтобы было наглядней, переберём попарно комбинации ограничений-прямых f1, f2, f3 и подготовим точки их пересечения P12, P13, P23 для отображения на графике:
точки пересечения прямых, соответствующих ограничениям задачи ЛП
Следующий этап, на самом деле, будет выполнен после построения графика - нужно подобрать подходящий для отображения области допустимых решений интервал [a,b] по оси X, а также любую точку Seed, лежащую внутри многоугольника, образованного всеми прямыми-ограничениями. Затем для надёжности проверим, все ли ограничения неравенства выполняются внутри многоугольника ОДР. Если что-то не выполняется, исходное неравенство даст значение не 1, а 0, значит, нужно штриховать противоположную от Seed сторону прямой, многоугольник ОДР окажется разомкнутым. Это ещё не значит, что решения нет, подробнее см. в лекции по первой ссылке:
проверка выполнения исходных ограничений по тестовой точке, лежащей внутри ОДР
Всё готово для построения графика, вот каким наглядным он может быть:
графическое решение задачи ЛП в Mathcad
На первой вкладке свойств графика (войти в это окно можно двойным щелчком по графику) выставлены линии сетки, флажок "В одинаковом масштабе" и опция "Отображение осей по центру". Вторую вкладку ("Трассировка") пришлось настроить детальней: кривые 1 и 2 - красные линии, с толщиной 1 и 2 соответственно, чтобы было видно направление градиента. Если бы задача была на минимум, нужно было бы двигаться перпендикулярно красным линиям от толстой к тонкой, у нас максимум, значит - от тонкой к толстой. Кривые 3-5 - чёрные линии, они соответствуют нашим трём ограничениям. Графики 6-8 - точки с символом "кружок" размером 3, они покажут углы многоугольника ОДР. График 9 тоже точка, она изображена фиолетовым квадратиком и контролирует, правильно ли мы выбрали Seed. По графику видно, что решение - точка P13 = (2,3).
Скачать этот пример в архиве .zip с документом Mathcad 15 .xmcd (44 Кб)
23.12.2015, 00:12 [14813 просмотров]