Тема 5. Линейные задачи оптимизации.

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

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

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

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

Задача 10. Предприятие для производства двух видов продукции может использовать 48 станков типа А, 36 станков типа В и 12 станков типа С. По техническим условиям на производство единицы продукции первого вида требуется занять 4 станка А и 2 станка В, для производства единицы продукции второго вида требуется 2 станка А, 4 станка В и 2 станка С.

Прибыль от реализации одной единицы продукции первого вида – 3 тысячи рублей, второго вида – 4 тысячи рублей. Составить план выпуска продукции, обеспечивающий максимальную прибыль.

Решение. Составим математическую модель задачи. Обозначим через и соответственно количество единиц продукции первого и второго видов.

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

. (1)

Точно так же получим ограничения по станкам соответственно типов В и С:

, (2)

. (3)

По смыслу задачи: . (4)

Любой план , удовлетворяющий ограничениям (1)-(4), будет допустимым и даст предприятию прибыль (в тыс. руб.)

. (5)

Итак, математически задача отыскания оптимального плана производства изделий сводится к определению таких и , удовлетворяющих линейным ограничениям (1)-(4), которые доставляют максимум линейной функции (5).

Соотношения (1)-(5) образуют математическую модель задачи:

. (6)

Решим задачу (6) графическим методом. Для построения области допустимых значений строим соответствующие данным неравенствам граничные прямые: – (I),

– (II),

– (III)

по точкам пересечения с осями координат. Для прямой (I) это точки: , ; для (II): , ; прямая (III) параллельна оси . Выберем масштаб 1: 3 (рис. 1). Далее находим полуплоскости, в которых выполняются данные неравенства. Так неравенство определяет полуплоскость с граничной прямой (I), в которой расположена точка (, т.е. это неравенство удовлетворяется координатами точки ).

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

Рис. 1

Теперь обратимся к функции (5), которая носит название целевой. Линии уровня функции : – это семейство паралельных прямых. Построим одну из них, например, , ее вектор нормали и она проходит через начало координат.

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

Найдем координаты этой точки, решив систему уравнений:

Подставим найденные значения в (5):

.

Ответ. Максимальное значение прибыли 46 тыс. рублей обеспечивает план выпуска продукции: 10 ед. продукции первого вида и 4 ед. продукции второго вида.

Пример 2. Животное должно получать ежедневно не менее 18 единиц вещества А и не менее 20 единиц вещества В. Один килограмм I вида корма содержит 6 ед. вещества А и 5 ед. вещества В. Один килограмм II вида корма содержит 3 ед. вещества А и 4 ед. вещества В. Цена корма I вида 10 руб., II вида – 8 руб. за кг.

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

Решение. Обозначим через и кг соответственно количество кормов I и II видов, которые предполагается включить в рацион.

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

. (7)

Ограничение по содержанию вещества B в рационе имеет вид:

. (8)

Естественно также, что

. (9)

В принятых обозначениях стоимость рациона выражается в виде функции:

. (10)

Итак, задача сводится к определению , , удовлетворяющих линейным ограничениям (7)-(9), при которых линейная функция (10) достигает наименьшего значения. Математическая модель задачи:

. (11)

Решим ее графическим методом. Проведем построение аналогично примеру 1.

Областью допустимых решений задачи является выпуклая многогранная неограниченная область х₂ х₁ (рис.2).

Построим нулевую линию уровня

, тогда .

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

Так как , , то уравнение отрезка : , . Тогда (руб.)

Рис. 2

Ответ: задача имеет неединственное решение. Минимальная стоимость рациона кормления – 40 рублей, оптимальный рацион можно рассчитать по формулам: , , где .

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

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

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

Можно доказать, что каждой угловой точке выпуклого многогранника или выпуклой многогранной области соответствует взаимно однозначным образом опорное (базисное неотрицательное) решение эквивалентной системы уравнений.

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

, где (), .

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

Указанные свойства позволят в дальнейшем наметить общие методы решения таких задач.

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

ПРИМЕР. Решить задачу л. п. симплексным методом:

Нам будет удобно привести данную задачу к каноническому виду следующим образом. Введем новую дополнительную переменную y₁ такую, что будет выполняться равенство -x₁+3x₂+y₁=3. При этом, очевидно, y₁³ 0. Аналогично, для любых x₁, x₂, x₃, удовлетворяющих второму неравенству системы, существует переменная y₂³ 0 такая, что 2x₁ - 2x₂ + 2x₃ + y₂=1, и, наконец, существует y₃³ 0, что - x₁+4x₂-2x₃+y₃= 0 для x₁, x₂, x₃, удовлетворяющих третьему неравенству системы. Таким образом, исходная задача эквивалентна следующей:

Разрешим систему уравнений относительно введенных нами переменных y₁, y₂, y₃ и запишем ее в виде удобном для применения м.ж.и.:

Напомним, что переменные, относительно которых система разрешена (в нашем случае это y₁, y₂, y₃), называются базисными, а остальные - свободными. Если свободные переменные приравняем нулю, то получим базисное решение. В нашем случае оно будет выглядеть так:

x₁ = 0, x₂ = 0, x₃ = 0,

y₁ = 3, y₂ = 1, y₃ = 0.

Базисное решение, в котором все базисные переменные принимают неотрицательные значения, называется опорным решением. Таким образом, это опорное решение системы. Запишем систему и целевую функцию z в таблицу1. Такая таблица называется симплексной.

Таблица 1

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

z = - 2 (- x₁) + 4 (- x₂) - 3 (- x₃) + 2 * 1 или

z = 2x₁ - 4x₂ + 3x₃ + 2, то есть целевая функция записана в таблицу верно.

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

На данном примере рассмотрим алгоритм перехода от опорного плана к оптимальному.

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

Разрешающий столбец будем выбирать по наименьшему отрицательному элементу z - строки, кроме свободного члена. Выбранный столбец будем отмечать стрелкой. (В таблице 1 это столбец (- x₃).)

Для того чтобы выбрать разрешающую строку, разделим свободный член каждой строчки на элемент этой же строки, находящийся в выбранном столбце. Получаем в первой строке 3/3; во второй строке - 1/2; в третьей строке - 0 / (-2). Полученное таким образом отношение назовем симплексным отношением (с. о.), если оно больше нуля или имеет вид 0/a, где a > 0. В нашем случае 3/3 и 1/2 - симплексные отношения, а 0/(-2) не является симплексным отношением. Разрешающую строку будем выбирать по наименьшему симплексному отношению разрешающего столбца. В нашем примере надо выбрать вторую строку, так как 1/2 < 3/3. Пересчитываем элементы по правилам М.Ж.И.:

Таблица 2

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

z = 1 (- x₁) + 1 (- x₂) + 3/2 (- y₂) + 7/2 *1.

Так как все переменные неотрицательны, то каждое из первых трех слагаемых меньше или равно 0. Следовательно, наибольшее значение функция z будет принимать тогда, когда x₁ = x₂ = y₂ = 0. Базисные переменные в этом случае будут равны своим свободным членам, то есть y₁ = 3/2, x₃ = 1/2, y₃ = 1. В ответ обычно не выписывают значения дополнительных переменных y.

Таким образом, таблица 4 - последняя в решении задачи примера 6, который закончим, записав

ОТВЕТ: z_max = 3, 5 при x₁ = x₂ = 0, x₃ = 0, 5.

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

Задача.ЗаЗЗЗЗЗ ЗЗЗЗЗЗЗзз ПРИМЕР. Фирма должна отправить некоторое количество кроватей с четырех складов в три магазина. Запасы на складах соответственно: а ₁=19, а ₂=5, а ₃=8, а ₄=18, а потребности магазинов: в ₁=15, в₂=22, в ₃=13.

Матрица тарифов: - стоимость перевозки одной кровати (в долларах) со склада в магазин. Как следует спланировать перевозку кроватей для минимизации стоимости?

Решение. Так как то модель транспортной задачи закрытая, данная задача разрешима. Найдем первый опорный план методом наименьшей стоимости. Составляем первую распределительную таблицу 1. План в таблице невырожденный, так как занятых клеток m+n-1= =4+3-1=6. Найденный опорный план проверим на оптимальность. Для этого находим потенциалы строк u_i и столбцов v_j из условия, что u_i+v_j=c_ij для занятых клеток (с_ij - тарифы). Получим систему, содержащую шесть уравнений с семью неизвестными:

u₁+v₂=7, u₁+v₃=6, u₂+v₂=6, u₃+v₁=5, u₄+v₁=7, u₄+v₂=10.

Полагая u₁=0, находим v₂=7, v₃=6, u₂= -1, u₄=3, v₁=4, u₃=1.

Для проверки оптимальности опорного плана находим оценки свободных клеток по формуле W_ij=c_ij-(u_i+v_j).

Получим W₁₁=11, W₂₁=5, W₂₃=3, W₃₂=2, W₃₃=-1, W₄₃=0. Так как среди оценок есть отрицательные, то план перевозок не является оптимальным.

Таблица 1

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

6 + - 13 14 5

+

8 - 8

7 + - 11 15 3

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

Таблица 2

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

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

z_min=14× 7+5× 6+5× 6+8× 6+15× 7+3× 10=341.

В оптимальном плане среди оценок свободных клеток есть нулевая W₃₄=0, это говорит о том, что оптимальное решение не единственное. Для получения другого оптимального решения надо построить цикл для этой клетки и перераспределить груз по циклу:

14 5 17 2

+ -

3 - + 3

Получим другой оптимальный план:

.

Замечание. Выполнение условия очень важно в транспортной задаче. Для задачи размерностью m ´ n оно означает, что в базисное допустимое решение входит m + n-1 базисная переменная. Предположим, что баланс между спросом и предложением нарушен.

Как справится с дисбалансом?

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

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

При построении первого опорного плана могут возникнуть трудности, если на каком-то шаге, кроме последнего, удаляется одновременно из рассмотрения и строка и столбец. В этом случае из дальнейших рассмотрений следует исключить только одну из них. Другая будет ликвидирована при присвоении базисной переменной значения 0. В результате получается m+n-1 базисных переменных и столько же заполненных клеток (даже если некоторые базисные переменные обратились в 0).

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