Графический метод решения задач линейного

Программирования

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

В системе координат  строим многоугольник, который определяется системой ограничений. Целевая линейная функция  при фиксированном значении  является уравнением прямой , называемой опорной прямой.

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

Вершина, из которой выходит опорная прямая, дает максимальное значение, в которую приходит минимальное значение целевой функции. Определяем координаты этих вершин, и находим соответствующие значения целевой функции, подставляя координаты в выражение для целевой функции.

Пример. Решить графическим методом задачу линейного программирования: найти максимальное значение функции  при ограничениях

 

 

,

;

, .

 

Решение. В системе координат  на плоскости строим прямую  по двум точкам с координатами  и  в первой четверти, так как . Прямая делит плоскость на две полуплоскости, из которых нужно выбрать одну, удовлетворяющую первому неравенству в системе. Для этого возьмем точку  и подставим в неравенство. Если неравенство выполняется, то нужно заштриховать ту полуплоскость, в которой находится точка . Аналогично поступают с прямой . Получаем, что областью решений неравенств является четырехугольник .

Строим опорную прямую , и перемещаем ее параллельно себе в направлении вектора по четырехугольнику , определяем вершину выхода – точку В.

 

 

Находим координаты точки В, для этого решаем систему уравнений:

 

 

Найденные координаты точки  подставляем в целевую функцию, и определяем максимальное значение:

 

.

 

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

Алгоритм симплекс-метода решения задач

Линейного программирования

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

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

Для реализации симплекс-метода необходимо определить: 1) первоначальное допустимое решение задачи, 2) правило перехода к лучшему решению, 3) критерий проверки оптимальности найденных решений. Для этого составляются различные алгоритмы симплекс-метода. Рассмотрим один из них для нахождения максимального значения целевой функции на следующем примере.

Найти максимальное значение функции , если переменные  удовлетворяют системе ограничений:

 

 

1. Вводим новые переменные , с помощью которых неравенства системы преобразуем в уравнения:

 

 

У коэффициентов целевой функции меняем знак или записываем ее в виде . Заполняем первую симплексную таблицу, в нулевой строке записываем х ₁, х ₂ и  (свободные коэффициенты). В нулевом столбце – х ₃, х ₄, х ₅ и F. Заполняем эту таблицу по полученной системе уравнений и преобразованной целевой функции.

 

 

	5	3	15
	-2	3	6
	3	-1	3
	-2	-3	0

     

 

Проверяем критерий оптимальности на нахождение максимального значения: в последней строке все коэффициенты должны быть положительными. Этот критерий не выполняется, переходим к составлению второй таблицы.

2. Находим разрешающий элемент первой таблицы следующим образом. Среди элементов последней строки выбираем наибольший по модулю отрицательный коэффициент (это -3) и второй столбец принимаем как разрешающий. Если же все коэффициенты столбца неположительные, то .

Для определения разрешающей строки свободные коэффициенты делим на соответствующие элементы разрешающего столбца и выбираем минимальное отношение, при этом отрицательные коэффициенты не берем. Имеем , вторая строка является разрешающей. Пересечение разрешающей строки и столбца дает разрешающий элемент – это 3.

3. Заполняем вторую симплексную таблицу. Переменные на пересечении которых получаем разрешающий элемент, меняем местами, т.е.  и . Разрешающий элемент заменяем ему обратным, т.е. на . Элементы разрешающей строки и столбца (кроме разрешающего элемента) делим на разрешающий элемент. При этом у коэффициентов разрешающего столбца меняем знак.

Остальные элементы второй таблицы получаем по правилу прямоугольника из элементов первой таблицы. Для заполняемой клетки и клетки с разрешающим элементом составляем прямоугольник. Затем из элемента для заполняемой клетки вычитаем произведение элементов двух других вершин, деленное на разрешающий элемент. Покажем расчеты по этому правилу для заполнения первой строки второй таблицы:

 

.

 

Заполнение таблиц по таким правилам продолжаем до тех пор, пока не будет выполнен критерий. Имеем для нашей задачи еще две таблицы.

 

	х1	х4	b				х3	х2	b
х3	7	-1	9			х1
х2			2			х2
х5			5			х5			2
F	-4	1	6			F

 

 

4. Результат выполнения этого алгоритма записывают следующим образом. В заключительной таблице элемент, стоящий на пересечении строки  и столбца b, дает максимальное значение целевой функции. В нашем случае . Значения переменных по строкам равны свободным коэффициентам. Для нашей задачи имеем .

Существуют и другие способы составления и заполнения симплексных таблиц. Например, для этапа 1 в нулевой строке таблицы записывают все переменные и свободные коэффициенты. После нахождения разрешающего элемента по тем же правилам в следующей таблице заменяем переменную в нулевом столбце, а в строке нет. Все элементы разрешающей строки делим на разрешающий элемент, и записываем в новой таблице. Для остальных элементов разрешающего столбца записываем нули. Далее выполняем указанный алгоритм с учетом этих правил.

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