Введение в симплексный метод

Генерация задач линейного программирования и их решение без выполнения арифметических операций

Богомазов Р. Ю. Беседин Н. Т.,

1. Поиск оптимального решения перебором вершин многоугольника ограничений.

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

Расход сырья Sk на изделие I1	Расход сырья Sk на изделие I2	Запасы cырья Sk
2	3	S1 = 35
2	1	S2 = 21
1	4	S3 = 40
5	1	S4 = 45
C1 = 7	C2 = 5	Доход

Как организовать производство, чтобы доход от произведенной продукции был максимальным? Иначе, сколько изделий вида I₁ и сколько изделий вида I₂ нужно изготовить, располагая ограниченными запасами сырья, чтобы доход был максимальным?

Пусть Х₁ – количество изделий вида I₁, а X₂ – количество изделий вида I₂. Задача сводится к нахождению максимума целевой функции F(X₁, X₂) = 7X₁ + 5X₂ на множестве точек плоскости, удовлетворяющих системе нестрогих неравенств-ограничений, дополненной требованием неотрицательности переменных.

2X₁ + 3X₂  35,

2X₁ + X₂  21, (1)

X₁ + 4X₂  40,

5X₁ + X₂  45,

X₁  0,

X₂  0,

F(X₁, X₂) = 7X₁ + 5X₂  max.

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

X₂

X₁

Рис. 1 Многоугольник решений системы неравенств (1).

Геометрическое место точек на плоскости, координаты которых удовлетворяют ограничениям задачи (1), образует выпуклый многоугольник OABCEF, изображенный на рис. 1. Этот многоугольник называется многоугольником решений данной системы неравенств. Границы многоугольника решений изображаются на плоскости прямыми линиями, построенными по уравнениям, которые получаются из ограничений задачи (1) заменой знаков “” и “” на знак “=”.

2X₁ + 3X₂ = 35,

2X₁ + X₂ = 21,

X₁ + 4X₂ = 40,

5X₁ + X₂ = 45,

X₁ = 0,

X₂ = 0.

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

В следующем пункте показано, что максимум целевой функции достигается не внутри многоугольника ограничений, а на границе в его вершинах. Казалось бы, такая особенность задач линейного программирования должна существенно упростить их решение, так в нашем простом случае максимум целевой функции F(X₁, X₂) = 7X₁ + 5X₂ можно найти простым перебором вершин многоугольника OABCEF: О(0,0), A(0,10), B(4, 9), C(7, 7), E(8,5), F(9,0). Легко убедиться, что искомый максимум достигается в точке С(7, 7), F_мах= F(C)=F(7, 7)=84.

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

2. О достижимости максимума целевой функции в угловых точках многоугольника ограничений.

Запишем задачу (1) в общем виде.

А₁₁X₁ + A₁₂X₂  S₁,

A₂₁X₁ + A₂₂X₂  S₂,

…………………… (2)

A_k1X₁ + A_k2X₂  S_k,

X₁  0,

X₂  0,

F(X₁, X₂) = C₁X₁ + C₂X₂  max.

Утверждения следующих двух простых теорем являются следствием линейности ограничений задачи (2).

Теорема 1. На отрезке AB, соединяющем две какие-либо соседние вершины A и B, выпуклого многоугольника ограничений задачи (2) произвольно взяты точки M(X₁₁, X₂₁) и N(X₁₂, X₂₂). Если F(М)=F(N)=C, то и в любой другой точке P(X₁, X₂) отрезка АВ F(P)=F(X₁, X₂)=С.

Доказательство.

F(X₁₁, X₂₁) = C₁X₁₁ + C₂X₂₁ =С

F(X₁₂, X₂₂) = C₁X₁₂ + C₂X₂₂ =С.

А это означает, что точки M и N лежат на прямой C₁X₁ + C₂X₂ = С. По условию точки А и В тоже лежат на этой прямой, и поэтому во всех точках P(X₁, X₂), принадлежащих отрезку AB, функция F(X₁, X₂) = C₁X₁ + C₂X₂ принимает то же самое значение С.

Теорема 2. Если в двух соседних вершинах многоугольника ограничений A(X₁₁, X₂₁) и B(X₁₂, X₂₂) целевая функция F(X₁, X₂) = C₁X₁ + C₂X₂ принимает значения M₁ и M₂,

F(X₁₁, X₂₁) = C₁X₁₁ + C₂X₂₁= M₁,

F(X₁₂, X₂₂) = C₁X₁₂ + C₂X₂₂= M₂,

причем M₂ > M₁, то значения целевой функции в точках отрезка AB не могут превышать значения M₂.

Доказательство.

Предположим противное, т. е. пусть на отрезке AB есть такая точка K(X_1k , X_2k), отличная от точки В, что F(K) = F(X_1k, X_2k) = M_k > M₂. Тогда непрерывная функция F(X₁, X₂) = C₁X₁ + C₂X₂, изменяясь в точках отрезка AB от меньшего значения M₁ до значения M_k, неизбежно примет промежуточное значение M₂ в некоторой точке J(X_1J , X_2J) отрезка АВ, не совпадающей с точкой В. Но тогда согласно теореме 1 функция F(X₁ , X₂) = C₁X₁ + C₂X₂ должна принимать значение M₂ во всех точках отрезка AB, и поэтому F(K) = F(X_1k, X_2k) = M₂. Последнее утверждение противоречит предположению M_k > M₂, что и доказывает теорему.

Следствие 1. Максимум целевой функции F(X₁, X₂) = C₁X₁ + C₂X₂ достигается в вершинах многоугольника ограничений.

Действительно, максимум функции двух переменных F(X₁, X₂) = C₁X₁ + C₂X₂ не может достигаться внутри многоугольника ограничений, так как не выполняется необходимое условие экстремума: частные производные этой функции во внутренних точках многоугольника ограничений не равны нулю, а именно: , . Остается одно - максимум целевой функции достигается на границе области ограничений. А согласно теореме 2 значения целевой функции в точках отрезка, соединяющего две соседние вершины А и В многоугольника ограничений, не могут превышать значений F(А) и F(В).

Следствие 2. Максимальное значение целевой функции F(X₁, X₂) = C₁X₁ + C₂X₂ может достигаться в точках отрезка, соединяющего две соседние вершины А и В многоугольника ограничений, лишь при условии F(А) = F(В). В этом случае задача имеет бесчисленное множество решений.