12.3. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

Фонд рабочего времени: (чел.

Производственная мощность:

Металлические стержни:

Листовой металл:

Постоянные заказы:

Профсоюзное соглашение:

Условие неотрицательности:

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

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

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

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

12.3.1. Графическое решение задачи линейного программирования

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

Рис. 12.1. Графическое изображение неравенства

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

Предположим, что х Какую часть плоскости описывает данное неравенство? Схема поиска ответа на этот вопрос аналогична схеме, используемой в предыдущем примере. Во-первых, проведем прямую Обратимся к графику, изображенному на рис. 12.2 слева. Как и в предыдущем примере, проведенная прямая разделяет плоскость на три множества точек: точки, для которых принадлежащие прямой; точки, для которых принадлежащие области, лежащей ниже прямой; и точки, для которых принадлежащие области, лежащей выше указанной прямой.

Полезным приемом при определении недопустимой области на графике является следующая процедура. Необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением. Если неравенство не выполняется, то точка является недопустимой и принадлежит, следовательно, недопустимой области. Удобной для использования при подстановке в неравенство точкой является начало координат. Подставим в неравенство Получим Данное утверждение является верным, следовательно, начало координат — допустимое решение, и недопустимой областью является часть плоскости, лежащая по другую сторону прямой. Это отражено на графике, изображенном на рис. 12.2 справа.

Рис. 12.2. Графическое изображение неравенства

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

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

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

Время работы оборудования:

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

Для определения области, которую следует заштриховать, подставим в неравенство:

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

Рис. 12.3. Графическое изображение неравенства

Специальный ингредиент:

Проведем прямую:

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

Рис. 12.4. Графическое изображение неравенства

Рис. 12.5. Графическое изображение условий неотрицательности переменных

Условие неотрицательности: .

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

Нанеся все ограничения задачи на один график, получим:

Рис. 12.6. Графическое изображение ограничений примера 12.1

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

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

Рассмотрим алгоритм выбора объема производства, максимизирующего ежедневный общий доход фирмы. Целевая функция задачи имеет следующий вид:

Если задать в день, целевую функцию можно проиллюстрировать графически. Если затем придать Р другое значение, то новая прямая будет параллельна прямой, соответствующей значению Р = 100 ф. ст. в день (рис. 12.7.)

Рис. 12.7. Целевая функция

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

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

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

Рис. 12.8. Задача линейного программирования для примера 12.1

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

Вычтем уравнение (2) из уравнения (1):

Следовательно, в день. Подставив найденное значение в уравнение (2), найдем

Следовательно, в день.

Таким образом, чтобы получать максимальный ежедневный доход, фирма должна производить в день. Это сочетание объемов производства дает максимальное значение дохода: ст. в день.

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

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

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

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

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

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

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

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

Пример 12.5. Обратимся к примеру 12.2, в котором рассматривалось производство двух типов деталей к автомобилям. Необходимо определить объемы производства, при которых достигается максимальное значение общего дохода за неделю. Решение.

Допустимые области для каждого из ограничений задачи выглядят следующим образом:

Рис. 12.9. Ограничение на фонд рабочего времени: в неделю

Рис. 12.10. Ограничение на производственные мощности: деталей неделю и деталей в неделю

(кликните для просмотра скана)

Рис. 12.14. Ограничение на профсоюзное соглашение: деталей в неделю

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

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

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

В качестве контрольной линии уровня будем использовать прямую ст. в неделю).

Эта прямая проходит также через точку с координатами На рис. 12.15 она изображена пунктирной линией. Движение параллельно этой прямой в направлении увеличения дохода приводит нас в точку А, которая является последним допустимым решением.

Лимитирующими являются ограничения на:

Фонд рабочего времени: в неделю;

Листовой металл: кг в неделю.

Решив соответствующую систему уравнений, получим:

следовательно, и после подстановки значения х в систему получим значение

Рис. 12.15. Задача линейного программирования для выпуска деталей типа X и Y к автомобилям в неделю

Оптимальным ассортиментным набором является выпуск 1500 деталей типа X и 1250 деталей типа Y в неделю. Таким образом, максимальный доход за неделю составит:

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

Нетрудно установить, что значения остаточных переменных в ограничениях на производственные мощности равны 750 для деталей типа X и 500 для деталей типа а именно:

Остаточная переменная ограничения на металлические стержни:

следовательно,

Избыточная переменная ограничения на постоянные заказы:

следовательно,

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

следовательно,

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

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

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

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

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