Когда задача ЛП имеет всего две переменные, ее решение можно иллюстрировать графически, что способствует более полному восприятию сущности метода решения и соответствующего алгоритма решения. Для этой цели используем данные и модель примера 2:
.
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x1, x2 ≥ 0
В этой задаче число переменных n = 2, а число ограничений m = 2.
Для графического решения задачи необходимо:
- построить область допустимых решений D;
- построить линии уровня целевой функции f(x) = cTx = f0;, которые будут перпендикулярны вектору с;
- выбрать линию с максимальным уровнем: она пересекает множество D либо в одной вершине, либо в двух вершинах. В первом случае имеем одно оптимальное решение, а во втором случае – бесчисленное множество оптимальных решений.
На рис.1.1 изображены: а) выпуклое (ограниченное по расстоянию) множество допустимых решений D, б) линии уровня целевой функции f(x), перпендикулярные вектору с = (5, 4)Т. Линиямаксимального уровня проходит через вершину х* с координатами х1* = 3, х2* = 1.5, являющейся оптимальным решением задачи. Максимальное значение целевой функции в этой точке равно f* = f(x*) = 21000. Таким образом, искомое решение есть х* = (x1*, x2*)T = ( 3, 1.5) T, f* = f(x*) = 21000.
|
|
Очевидно, что найденные оптимальные значения х* и f* зависят от параметров задачи сj, j = 1, …, n, bi, i = 1, …, m, aij, i = 1, …, m, j = 1, …, n, другими словами, х* = х*(с, b, А), f* = f*(с, b, А). Поэтому, перед тем, как рекомендовать найденное решение к внедрению, необходимо провести его анализ чувствительности, т. е. решить вопрос о том, как влияют параметры задачи на оптимальное решение.
Рис. 1.1. Графическая иллюстрация решения.