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

В данном разделе будет рассмотрен процесс нахождения значений переменных, которые удовлетворяют системе ограничений и оптимизируют целевую функцию задачи. Однако гораздо удобнее исследовать не систему неравенств, а систему уравнений. Процесс преобразования неравенств в уравнения достаточно прост. Для этого в левую часть неравенства вводится дополнительная переменная. Эта переменная призвана отразить величину разности между правой и левой частями неравенства. Чтобы продемонстрировать этот алгоритм, обратимся к примеру 1.2, в котором рассматривается производство деталей типов Х и Y к автомобилям. Для получения системы уравнений в каждое ограничение введем дополнительную переменную. Обозначим данную переменную через s, таким образом, в первое ограничение вводится переменная s₁ во второе — s₂ и т.д. Кроме того, примем предпосылку о неотрицательности значений этих переменных, т.е. s_i 0. Это значит, что дополнительные переменные прибавляются к левым частям всех ограничений знака " " и вычитаются из левых частей ограничений знака " ". Задача линейного программирования в данном случае принимает следующий вид: производится х деталей типа Х и у деталей типа Y в неделю. Цель состоит в максимизации общего дохода в неделю. Максимизировать:

Р = 30 х + 40 у (ф. ст. в неделю)

при ограничениях:

Фонд рабочего времени: l x + 2 y + s₁ = 4000 (чел.-ч/нед.)

Производственная мощность: х + s₂ = 2250 (деталей/нед.)

у + s₃ = 1750 (деталей/нед.)

Металлические стержни: 2 х + 5 y + s₄ = 10000 (кг/нед.)

Листовой металл: 5 х + 2 у + s₅ = 10000 (кг/нед.)

Постоянные заказы: х – s₆ = 600 (деталей/нед.)

Профсоюзное соглашение: х + у – s₇ = 1500 (деталей/нед.)

Условие неотрицательности: х, у 0

Такие вспомогательные переменные для ограничений со знаком " " называются остаточными переменными. Они представляют собой количество недоиспользуемого ресурса, т.е. разность между используемым количеством ресурса и его максимальным объемом. Рассмотрим, например, ограничение на фонд рабочего времени, указанное выше. Предположим, что в течение недели выпускается 1000 деталей каждого типа, тогда используемое число человеко-часов составит: 1х1000 + 2х1000 = 3000. Поскольку максимальный фонд рабочего времени равен 4000 чел.-ч., резерв времени, или остаток, составит: 4000 - 3000 = 1000 чел.-ч. Следовательно, для данной комбинации х - у и s₁ принимают значение, равное 1000.

Вспомогательные переменные, используемые в ограничениях типа " ", называются избыточными переменными, так как они показывают количество ресурса, используемое сверх минимального его объема. Рассмотрим, к примеру, ограничение на постоянные заказы в случае, когда выпускается 1000 деталей типа X. Минимальное число деталей типа Х составляет в соответствии с данным ограничением 600 штук, следовательно, уровень производства, равный 1000 деталей, порождает излишек в 400 штук сверх минимального количества. Таким образом,s₆ принимает значение, равное 400

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

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