Нахождение решения задачи линейного программирования на основе её геометрической интерпретации

 

Найдём решение задачи (записанной в форме стандартной), состоящей в определении максимального значения функции L = c ₁ x ₁ + c ₂ x ₂ при условиях

a_{i 1} x ₁ + +a_{i 2} x ₂ ≤b_i (i= 1 ,…,k),

x_j ≥ 0 (j = 1,2 ).

Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость с граничными прямыми a_{i 1} x ₁ + a_{i 2} x ₂ = b_i (i = 1, …, k), х ₁ = 0 и х ₂=0. В том случае, если система неравенств совместна, область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то областью допустимых решений задачи является выпуклое множество, которое называется многоугольником решений (многогранником, когда n ≥3). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой целевая функция L принимает максимальное значение (для стандартной задачи линейного программирования). Эта точка существует тогда, когда многоугольник решений не пуст, и на нём целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня с ₁ х ₁ +с ₂ х₂=h (где h – некоторая постоянная), проходящую через многоугольник решений, и будем передвигать её в направлении вектора =(с ₁ ;с ₂ ) до тех пор, пока она не пройдёт через последнюю её общую точку с многоугольником решений. Координаты указанной точки и определят оптимальный план данной задачи.

Заканчивая рассмотрение геометрической интерпретации задачи линейного программирования, отметим, что при нахождении её решения могут встретиться случаи, изображённые на рисунках 5.1-5.4. Рисунок 5.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке A.

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

Рисунок 5.4 – Случай 4

Рисунок 5.3 – Случай 3

Рисунок 5.2 – Случай 2

Рисунок 5.1 – Случай 1

 

Отметим, что нахождение минимального значения линейной целевой функции при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня с ₁ х ₁ +с ₂ х ₂ =h передвигается не в направлении вектора =(с ₁ ;с ₂ ), а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении её минимального значения.

Итак, нахождение решения задачи линейного программирования на основе её геометрической интерпретации включает следующие этапы:

1. Строят прямые, уравнения которых получают в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Находят многоугольник решений.

4. Строят вектор =(с₁;с₂).

5. Строят прямую с₁х₁+с₂х₂=h, проходящую через многоугольник решений.

6. Передвигают прямую с₁х₁+с₂х₂=h в направлении вектора , в результате чего-либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.

7. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

Рассмотрим пример.

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

 

Таблица 5.3 – Условия задачи оптимального использования сырья

 

Вид сырья	Нормы расхода сырья (кг) на одно изделие		Общее количество
	A	B	сырья (кг)
I II III	12 4 3	4 4 12	300 120 252
Прибыль от реализации одного изделия (руб.)	30	40

 

Учитывая, что изделия А и В могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий является максимальной.

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

Общая прибыль от реализации  изделий вида А и  изделий вида В составит F =30 + 40 .

Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значение.

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

Эти прямые изображены на рисунке 5.5. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли её координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае – другая полуплоскость.

Найдем, например, полуплоскость, определяемую неравенством 12 +4 <300. Для этого, построив прямую 12 +4 =300 (пр. I), возьмём какую-нибудь точку, принадлежащую одной из полученных полуплоскостей, например, точку O(0;0). Координаты этой точки удовлетворяют неравенству: 12 , значит, полуплоскость, которой принадлежит точка O(0;0), определится неравенством 12 .

Это и показано стрелками на рисунке 5.5.

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

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

Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику OABCD, в которой функция F принимает максимальное значение. Чтобы найти указанную точку, построим вектор  и прямую 30 , где h – некоторая постоянная такая, что прямая 30   имеет общие точки с многоугольником решений. Положим, например, h =480 и построим прямую 30  (рисунок 5.5). Точки пересечения с осями .

 

 

0

10

20

25

30

40

50

60

70

80

90

100

94

10

20

30

40

50

60

70

21

75

А

BBBBBBВDD

С

D

C

X2

(V

(IV)

(II)

12х1 + 4х2 = 300 (I)

4x1 + 4x2 = 120 (II)

30x1 + 40x2 = 480

30x1 + 40x2 = 1080

3x1 + 12x2 =252 (III)

X1

 

 

Рисунок 5.5 –  Геометрический метод решения примера 5.1

 

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

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

Найдем координаты точки В как точки пересечения прямых II и III. Следовательно, её координаты удовлетворяют уравнениям этих прямых:

Решив эту систему уравнений, получим =12, =18. Следовательно, если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную =  руб.

Вообще, с помощью графического метода может быть решена такая задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если n и m связаны соотношением n - m =2.

Действительно, пусть поставлена каноническая задача линейного программирования: найти минимальное значение линейной функции Z =  при ограничениях

где все уравнения линейно независимы и выполняется соотношение n - m = 2.

Используя метод Гаусса, производим m исключений, в результате которых базисными неизвестными оказались, например, m первых неизвестных , а свободными – два последних  и , т.е. система ограничений приняла вид:

 

(4.6)

 

  (j = 1,2,…, n).

С помощью уравнений преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные переменные - неотрицательные (, j = 1,2,…, n),отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств. Таким образом, окончательно получаем следующую задачу:

Найти минимальное значение линейной функции Z =    при ограничениях

Преобразованная задача содержит две неизвестных; решая её геометрическим способом, находим оптимальные значения  и , а затем, подставляя их в (5.4), находим оптимальные значения .

 

Контрольные вопросы

 

1. Задача линейного программирования в общем виде.

2. Перечислите озможные варианты решения задачи линейного программирования.

3. Назовите области применения линейного программирования.

4. Пример решения станковой задачи.

5. Математическая модель задачи использования сырья.

6. Основные понятия и теоремы линейного программирования: допустимый, опорный план, теорема связи опорных планов задачи с угловыми точками выпуклого множества.

7. Формы записи задачи линейного программирования: каноническая, стандартная, общая.

8. Нахождение решения задачи линейного программирования на основе её геометрической интерпретации.