Графический способ решения задачи

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Лекция 3. РЕШЕНИЕ И АНАЛИЗ ЗАДАЧИ

1. Графический способ решения задачи

2. Симплексный метод и его алгоритм

3. Решение задачи симплексным методом

4. Симплекс-метод с искусственным базисом (М-метод)

Задача линейного программирования в простейшем случае может быть решена графическим способом. Он применим при решении задач небольшой размерности, когда число переменных не превышает трех.

Рассмотрим сельскохозяйственную задачу из темы 2:

Для решения рассматриваемой задачи построим прямоугольную систему координат. По оси абсцисс (горизонтальная ось) отложим возможные зна­чения переменной х₁, а по оси ординат (вертикальная ось) – возможные значения переменной x₂. Эти оси разбивают плоскость на четыре квадранта (рис. 2). Определим на графике область допустимых решений задачи, т.е. множество допустимых вариантов пла­на.

х₂

4

2

2 4 6 х₁

Рис. 2 - Построение граничной прямой

1. Искомые площади под сахарной свеклой и зерновыми культурами не могут быть отрицательными. Следовательно, допустимыми являются только варианты, на­ходящиеся в I квадранте. По условиям задачи пашня со­ставляет 5 га; это ограничение было записано как неравенства х₁+х₂5. Такое неравенство делит I квадрант на две полуплоскости, на одной из которых все точки ему удовлетворяют, на другой – не удовлетворяют. Разделительная прямая между полуплоскостями называется граничной прямой. Все точки этой прямой удовлетворяют равенству х₁+х₂=5. Следовательно, достаточно построить пря­мую, соответствующую данному уравнению, как полу­плоскости будут определены.

Для построения прямой необходимо найти любые две ее точки. Приравняв одну из переменных нулю, оп­ределим значение другой: при х₁=0, х₂=5; при х₂=0, х₁=5.

Итак, граничная прямая, соответствующая неравен­ству х₁+х₂5, проходит через точки с координата­ми (0; 5) и (5; 0). Нанесем граничную прямую на график (рис. 2).

Определим, какая из полуплоскостей включает на­чало координат (х₁=0, х₂=0). Подставив в неравенство х₁+х₂5 значения х₁=0 и х₂=0, получим 0<5, т.е. начало координат удовлетворяет неравенству. Это значит, что и все точки полуплоскости, включаю­щей начало координат, удовлетворяют неравенству. На рисунке 2 эта полуплоскость показана стрелками от гра­ничной прямой.

2. Рассмотрим на графике второе неравенство, от­ражающее ограничение по трудовым ресурсам: 30x₁+150x₂300. Чтобы найти граничную прямую, за­меним неравенство на уравнение: 30x₁+150x₂=300. Приняв x₁=0, получим: 150x₂=300, откуда x₂=2. Следовательно, граничная прямая второго неравенст­ва проходит через точку (0; 2). Находим вторую точку этой граничной прямой, приравняв x₂ нулю: 30x₂=300, откуда x₁=10. Следовательно, вторая точка, через которую проходит граничная прямая, име­ет координаты (10; 0).

Экономический смысл рассматриваемых величин со­стоит в следующем: имеющиеся трудовые ресурсы (300 чел.–дн.) позволяют возделывать либо 2 га сахарной свеклы (при этом 3 га пашни остались бы неис­пользованными), либо 10 га зерновых культур (но в хозяй­стве имеется всего 5 га пашни).

х₂

6

4 (1)

С

А

(2)

В

2

ОДР

0 2 4 6 8 10 х₁

Рис. 3 - Определение области допустимых решений задач

Нанесем на график (рис. 3) найденные точки с коорди­натами (0; 2) и (10; 0), соединим их прямой (2), являющейся граничной для неравенства, выра­жающего ограничение по трудовым ресурсам.

Определим, какая полуплоскость удовлетворяет это­му неравенству. Приняв х₁=0 и х₂=0, убедимся в том, что неравенству удовлетворяет полуплоскость, распо­ложенная ниже граничной прямой (эта полуплоскость включает начало координат, так как при х₁=0 и х₂=0 имеем 0<300).

Граничные прямые системы неравенств (1,2), на­несенные на график, отсекают на плоскости I квадранта выпуклый многоугольник OABC (рис.3). Любая точка данного многоугольника (включая и точки, ле­жащие на его граничной прямой) удовлетворяет одно­временно всем ограничениям задачи. Поэтому мно­жество точек этого многоугольника представляет собой область допустимых решений (ОДР) задачи (допустимых вариантов плана).

В теории линейного программирования доказыва­ется, что экстремальное значение целевой функции обя­зательно достигается на границе выпуклого много­гранника с конечным числом угловых точек. Такой мно­гогранник называется симплексом. Отсюда произошло название симплексного метода решения задач линей­ного программирования путем направленного перебора вершин симплекса до получения оптимального плана. Следовательно, оптимальный вариант плана можно отыскать, последовательно перебирая варианты соче­тания х₁ и х₂ на вершинах многоугольника. Определим по графику (рис. 3) координаты вершин многоугольника и найдем соответствующие значения целевой функции (табл. 3).

Таблица 3 – Значение переменных и условий функции

в задаче линейного программирования

Вершина ДОР	Координаты	Значение целевой функции, тыс. руб.
O	0; 0
А	0; 2
В	3, 1	27,5
С	5; 0

Таким образом, максимальное значение целевой функции достигается в вершине В, что соответствует варианту плана, когда площадь зерновых (х₁) составляет 3,75 га и площадь сахарной свеклы (х₂) – 1,25 га.

Однако решение задачи путем последовательного рассмотрения всех вершин многоугольника трудоемко. Более эффективен следующий способ. Возьмем целевую функцию задачи Z_max=4x₁+10x₂. Ей можно при­дать любое произвольное значение (например, вычислив или приблизительно определив значение Z для любой точки многоугольника допустимых решений задачи). Допустим, Z=20 тыс. руб., т.е. Z=4х₁+10х₂=20. Построим на графике прямую, соответствующую этому уравнению. При х₁=0 имеем 10х₂=20, откуда х₂=2; при х₂=0 имеем 4х=20, откуда х₁=5. Следовательно, прямая, соответствующая уравнению 4х₁+10х₂=20 проходит через точки с координатами (0; 2) и (5; 0) (рис. 4). Прямую, соответствующую целевой функции, называют линией уровня (разрешающей линией).

х₂

А

F_max=27,5

F=20

0 2 4 С 6 х₁

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

Поскольку экстремальное значение целевой функции обязательно достигается на поверхности выпуклого многогранника, то следует передвигать разрешающую линию параллельно самой себе до тех пор, пока она не коснется крайней точки выпуклого многогранника. В рассматриваемом примере такой точкой является вершина В (рис. 4). Координаты найденной вершины и соответствуют оптимальному вари­анту плана.

Иногда разрешающая линия может совпадать с од­ной из сторон многоугольника. Это означает, что дан­ная задача имеет не одно, а множество оптимальных решений, так как координаты любой точки данной сто­роны многоугольника будут приводить к одному и тому же значению целевой функции.

Удобным и простым способом нахождения точки экстремума целевой функ­ции является определение вектора-градиента, который показывает направление максимизации целевой функ­ции. Чтобы построить вектор-градиент на графике, до­статочно определить две точки. Начальная точка век­тора-градиента совпадает с началом координат. В качестве координат конечной точки вектора-градиента принимаются коэффициенты целевой функ­ции (4; 10)¹.

Из теории линейного программирования известно, что вектор-градиент и разрешающая линия взаимно перпендикулярны. Передвигая разрешающую линию параллельно самой себе по направлению векто­ра-градиента, можно найти крайнюю точку В выпуклого многогранника, соответствующую оптимальному плану.

Дата добавления: 2014-01-05