Лекция 1 Графический метод решения задач линейного программирования
Опубликовано: 01.09.2017
Геометрический (графический) метод можно использовать для решения:
1) задач линейного программирования с двумя переменными, представленных в стандартной форме;
2) задач линейного программирования со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных
Решение задач линейного программирования графическим методом в общем виде можно представить последовательностью следующих этапов:
Лекция 2: Задача линейного программирования. Задача о ресурсах
1. Записать в виде y=kx+b уравнения прямых, ограничивающих область допустимых значений переменных.
2. Изобразить на графике соответствующие прямые и определить область допустимых значений переменных.
3. Построить для одного или нескольких значений С линии уровня целевой функции f(x, y)=C (несколько линий уровня необходимо построить для того, чтобы понять, имеет ли задача решение и где достигается искомый экстремум).
4. Если задача имеет единственное решение, найти вершину, в которой достигается искомое экстремальное значение (максимум или минимум) целевой функции, и определить ее координаты.
5. Вычислить значение целевой функции в найденной точке.
6. Если задача имеет бесконечное множество решений (т.е. экстремум достигается на отрезке, луче или прямой), то вычислить значение целевой функции в одной из точек, принадлежащих данному отрезку (лучу, прямой) и описать множество решений.
7. Сформулировать общий вывод по задаче линейного программирования.
Пример 6.6. Решить следующую задачу линейного программирования графическим методом:
Фрагменты рабочего документа MathCAD с решением данной задачи представлены на рис. 44 – 49.
Рис. 44. Фрагмент MathCAD-документа: определение уравнений прямых, ограничивающих область допустимых решений задачи
Рис. 45. Фрагмент MathCAD-документа:
область допустимых решений задачи
Для удобства работы MathCAD позволяет перемещать любые графические объекты на передний или задний план рисунка. Для этого необходимо навести курсор мыши на графической объект, щелкнуть правой кнопкой мыши и выбрать пункт меню Bring to Front(на передний план), Send to Back (на задний план). Поэтому для того, чтобы в дальнейшем буквы, обозначающие точки на графике, или стрелки были доступны для редактирования и перемещения необходимо график, на который они наложены, поместить на задний план. Для этого на графике необходимо щелкнуть правой кнопкой мыши и выбрать пункт меню Send to Back(рис. 46).
Рис. 46. Фрагмент MathCAD-документа: использование контекстного меню для перемещения графических объектов на передний или задний план
Рис. 47. Фрагмент MathCAD-документа:
построение целевой функции F(x) и вектора-градиента С
Рис. 48. Фрагмент MathCAD-документа:
нахождение координат точки С и максимума целевой функции
Рис. 49. Фрагмент MathCAD-документа:
построение окончательного графика
Пример 6.7. Решить следующую задачу линейного программирования графическим методом:
Фрагменты рабочего документа MathCAD с решением данной задачи представлены на рис. 50 – 53.
Рис. 50. Фрагмент MathCAD-документа: приведение исходной задачи линейного программирования к стандартной форме
Рис. 51. Фрагмент MathCAD-документа:
исходная задача линейного программирования в стандартной форме
Рис. 52. Фрагмент MathCAD-документа: определение уравнений прямых, ограничивающих область допустимых решений задачи
Рис. 53. Фрагмент MathCAD-документа:
построение области допустимых решений задачи
