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

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

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

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

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

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

4. Строят вектор  .

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

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

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

Пример 7.

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

Таблица 2

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

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

      Общая прибыль от реализации x₁ изделий вида А и изделий вида В составит

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

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

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

      Найдем, например, полуплоскость, определяемую неравенством Для этого, построив прямую (на рис. 5 эта прямая I), возьмем какую-нибудь точку, принадлежащую одной из двух полученных полуплоскостей, например точку О(0; 0). Координаты этой точки удовлетворяют неравенству значит, полуплоскость, которой принадлежит точка О(0; 0), определяется неравенством Это и показано стрелками на рис. 5.

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

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

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

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

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

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

Пример 8.

      Найти максимум и минимум функции  при условиях

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

      Построив  полученные прямые, найдем соответствующие  полуплоскости и их пересечение (рис. 6).

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

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

      Решив эту систему уравнений, получим Таким образом, максимальное значение функции

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

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

СИМПЛЕКС-МЕТОД.

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

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

      Пусть требуется найти максимальное значение функции

при условиях

      Здесь и – заданные постоянные числа

Векторная форма данной задачи имеет следующий  вид: найти максимум функции

(22)

при условиях

(23)

(24)

где

Так как

      то  по определению опорного плана  является опорным планом данной задачи (последние компонент вектора Х равны нулю). Этот план определяется системой единичных векторов которые образуют базис m-мерного пространства. Поэтому каждый из векторов а также вектор могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть

Положим Так как векторы – единичные, то и а

Теорема 5

(признак  оптимальности опорного плана). Опорный план задачи (22) – (24) является оптимальным, если для любого j

Теорема 6.

      Если для некоторого j=k и среди чисел нет положительных , то целевая функция (22) задачи (22) – (24) не ограничена на множестве ее планов.

Теорема 7.

      Если  опорный план Х  задачи (22) – (24) невырожден и , но среди чисел есть положительные (не все ), то существует опорный план X' такой, что

      Сформулированные  теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.

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

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

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

В табл. 3 первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора – значение

Значение  Z_j находится как скалярное произведение вектора на вектор

Значение  равно скалярному произведению вектора P₀ на вектор :

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