БлогNot. Решение задачи линейного программирования графическим методом - как проиллюстрир...

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

Решение задачи линейного программирования графическим методом - как проиллюстрировать в Mathcad?

Теория приведена, например, здесь (лекция 3). Отметим, что простейшим графическим методом решается задача только для двух неизвестных с линейной целевой функцией. Но рисовать на бумаге, что вышло, мне лично было бы лень.

Можно сделать похитрее и поавтоматизированней, чем в примере, например, попытаться автоматически штриховать область допустимых решений (ОДР), но не будем усложнять простую вещь.

Вот каким алгоритмом сделать понятнее всего. Возьмём классическую задачу линейного программирования (ЛП):

постановка задачи
постановка задачи

Ограничения на неотрицательность x1, x2 тривиальны, а остальные определим как функции 2 переменных r1, r2, r3. Для построения графиков прямых, соответствующих этим трём ограничениям, решим их относительно переменной x2 как равенства, получатся функции f1(x1), ..., f3(x1):

представление ограничений задачи ЛП как уравнений прямых в Mathcad
представление ограничений задачи ЛП как уравнений прямых в Mathcad

Целевую функцию зададим как z(x1,x2), определим для неё 2 любых различных тестовых значения, Level1 и Level2. Они понадобятся, чтобы увидеть на графике направление возрастания функции (вектор градиента, перпендикулярный обеим линиям и направленный от z(x1,x2)=Level1 к z(x1,x2)=Level2):

определение целевой функции для задачи ЛП в Mathcad
определение целевой функции для задачи ЛП в Mathcad

Чтобы было наглядней, переберём попарно комбинации ограничений-прямых f1, f2, f3 и подготовим точки их пересечения P12, P13, P23 для отображения на графике:

точки пересечения прямых, соответствующих ограничениям задачи ЛП
точки пересечения прямых, соответствующих ограничениям задачи ЛП

Следующий этап, на самом деле, будет выполнен после построения графика - нужно подобрать подходящий для отображения области допустимых решений интервал [a,b] по оси X, а также любую точку Seed, лежащую внутри многоугольника, образованного всеми прямыми-ограничениями. Затем для надёжности проверим, все ли ограничения неравенства выполняются внутри многоугольника ОДР. Если что-то не выполняется, исходное неравенство даст значение не 1, а 0, значит, нужно штриховать противоположную от Seed сторону прямой, многоугольник ОДР окажется разомкнутым. Это ещё не значит, что решения нет, подробнее см. в лекции по первой ссылке:

проверка выполнения исходных ограничений по тестовой точке, лежащей внутри ОДР
проверка выполнения исходных ограничений по тестовой точке, лежащей внутри ОДР

Всё готово для построения графика, вот каким наглядным он может быть:

графическое решение задачи ЛП в Mathcad
графическое решение задачи ЛП в Mathcad

На первой вкладке свойств графика (войти в это окно можно двойным щелчком по графику) выставлены линии сетки, флажок "В одинаковом масштабе" и опция "Отображение осей по центру". Вторую вкладку ("Трассировка") пришлось настроить детальней: кривые 1 и 2 - красные линии, с толщиной 1 и 2 соответственно, чтобы было видно направление градиента. Если бы задача была на минимум, нужно было бы двигаться перпендикулярно красным линиям от толстой к тонкой, у нас максимум, значит - от тонкой к толстой. Кривые 3-5 - чёрные линии, они соответствуют нашим трём ограничениям. Графики 6-8 - точки с символом "кружок" размером 3, они покажут углы многоугольника ОДР. График 9 тоже точка, она изображена фиолетовым квадратиком и контролирует, правильно ли мы выбрали Seed. По графику видно, что решение - точка P13 = (2,3).

 Скачать этот пример в архиве .zip с документом Mathcad 15 .xmcd (44 Кб)


теги: графика учебное mathcad

показать комментарии (1)

23.12.2015, 00:12; рейтинг: 6859

  свежие записипоиск по блогукомментариистатистика

Наверх Яндекс.Метрика
© PerS
вход