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

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

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

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

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

1) ЗЛП в общем виде.

Необходимо исследовать на экстремум функцию

max (min) (1.1)

при условиях

(1.2)

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

Целевая функция (1.1) и ограничения в системе (1.2) являются линейными функциями от переменных , .

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

В матричной форме задачу (1.1) – (1.2) можно представить так:

max(min)

АХ b,

.

А – m n-матрица из коэффициентов при переменных в (1.2), b – m 1-матрица-столбец из свободных членов (1.2), Х – n 1-матрица-столбец из неизвестных.

ЗЛП в каноническом виде.

Оптимизировать функцию

max (1.3)

при условиях

АХ = b , (1.4)

(1.5)

где .

Для применения большинства методов решения задачу (1.1)-(1.2) необходимо привести к каноническому виду(1.3)-(1.5), используя следующие правила:

· Если необходимо минимизировать целевую функцию, т.е. решить задачу: , то для приведения к виду (1.3) необходимо изменить знак целевой функции: .

· Условие , к виду (1.5) приводится заменой , где .

· Условие любое число, к виду(1.5) приводится заменой , где .

· Ограничение, заданное неравенством вида АХ b, к виду (1.4) приводится введением дополнительной переменной : АХ + = b, где .

· Ограничение, заданное неравенством вида АХ b, к виду (1.4) приводится введением дополнительной переменной : АХ – = b, где .

 

Пример. Задача о диете.

Имеется два вида продуктов: x и y. Один килограмм продукта х стоит 25 рублей и содержит 10 единиц питательного вещества а и 12 единиц питательного вещества b. Один килограмм продукта устоит 37 рублей и содержит 15 единиц питательного вещества аи 20 единиц питательного вещества b. Необходимый минимум в диете – 30 единиц а и 40 единиц b. Составить диету минимальной стоимости.

  х у
а
b

 

Пусть Z – целевая функция. Тогда

 

Z = 25х + 37у min.

Введем ограничения на переменные:

Итак, если

- если система ограничений состоит из нестрогих неравенств стандартная

задача линейного программирования;

- если система ограничений состоит только из равенств каноническая задача;

- от стандартной задачи можно перейти к канонической добавлением новых вспомогательных переменных;

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

 

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

Графический метод.

Постановка задачи:

Необходимо оптимизировать функцию

(2.1)

при условиях (2.2)

(2.3)

где , и .

Если задача (2.1)-(2.3) содержит не более 3 переменных (n = 2), то ее решение можно легко найти графически по алгоритму, основанному на известных из курса математического анализа свойствах линейной функции двух переменных:

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

б) вектор grad f(x1, х2,…,хn ) = - вектор наискорейшего роста функции f(x1, х2,…,хn) (при n=2: grad f(x,y) = )

вектор - grad f(x,y) - вектор наискорейшего убывания функции f(x,y);

в) вектор grad f(x,y) перпендикулярен линии уровня .

 

 

Алгоритм графического метода решения ЗЛП (вида (2.1)-(2.3)):

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

2. Найти градиент grad f(x,y) целевой функции (2.1) в случае максимизации и (- grad f(x,y)) в случае минимизации.

3. Построить вектор градиента из начала координат.

4. Построить линию уровня целевой функции (2.1) – прямую , перпендикулярную вектору градиента, которая представляет график линейной функции (n = 2).

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

6. Идентифицировать точку экстремума в зависимости от направления оптимизации функции.

 

Замечание.

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

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

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

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

Постановка задачи:

Необходимо оптимизировать функцию

(2.4)

при условиях (2.5)

(2.6)

где . Необходимо выполнение условия: (или ).

Алгоритм графического метода решения ЗЛП (вида (2.4)-(2.6)):

1. Привести систему ограничений (2.5) к виду

(2.7)

 

Переменные называются базисными (или базисом), при этом каждая переменная присутствует только в одном уравнении с коэффициентом +1 и отсутствует в остальных уравнениях. Переменные называются небазисными.

2. Выразить базисные переменные через небазисные:

, . (2.8)

3. Заменить базисные переменные в целевой функции на их выражение через небазисные (2.8). Получим новую целевую функцию:

(2.9)

4. Используя неравенство (2.6), получим , , тем самым перейдем к системе ограничений (2.10):

 

(2.10)

(2.11)

5. Выполнить шаги 1-6 алгоритма графического метода решения ЗЛП (вида (2.1)-(2.3)) для задачи (2.9)-(2.11).

6. Найти значения базисных переменных по формуле (2.8). Вектор является решением исходной задачи (2.4)-(2.6).

 

Пример 1. Шоколадная фабрика (целью которой является максимизация прибыли) производит два вида продукции: шоколад и конфеты (рыночная цена которых 4 и 5 тыс. у.е. за тонну), из двух видов сырья: какао-бобов и орехов. За один период фирма может закупить не более 12 тонн какао-бобов и 8 тонн орехов. При этом для производства 1 тонны шоколада необходимо 5 т. какао-бобов и 2 т. орехов, а для производства 1 т. конфет 2 т. какао-бобов и 4 т. орехов. Сколько тонн шоколада и конфет нужно произвести, чтобы прибыль фабрики была наибольшей?

Решение. Составим модель производства продукции. Обозначим производимые продукты за x (шоколад) и y (конфеты). Т.к. целью фирмы является максимизация прибыли, целевой функцией следует выбрать функцию прибыли данного предприятия.

Соответственно, на производство шоколада потребуется 5x т. какао-бобов, а на производство конфет 2y т. При этом может быть затрачено не более 12 т. данного сырья.

Аналогично и для второго ингредиента – орехов: ;

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

Система описывает множество пар объемов продукции, которые может производить фирма при ограниченных ресурсах.

Решим данную задачу графически.

Рис.1.

Ответ: Шоколадная фабрика должна произвести 2 тонны шоколада и 1 тонну конфет, чтобы прибыль была наибольшей.

Применим графический метод для решения задачи.

Пример 2. С целью обеспечения высокого объема перевозок железная дорога имеет возможность рекламировать свою деятельность, используя местные радио и телевизионные сети. Затраты на рекламу ограничены величиной 3000 условных денежных единиц. Каждая минута радиорекламы обходится в 20 условных денежных единиц, а минута телерекламы – в 60 единиц. Исходя из своих конъюнктурных соображений, железная дорога хотела бы использовать радиосеть по крайней мере в 2 раза чаще, чем телесеть. Радиокомпания согласна предоставить рекламное время в объеме не более 100 минут. Одна минута телерекламы обеспечивает объем перевозок в 6 раз превышающий объем перевозок, обеспечиваемый радиорекламой. Найти оптимальное распределение финансовых средств между телевизионной и радиорекламой.

Обозначим за х1 и х2 количество времени, затрачиваемого на радио и телерекламу, соответственно. Если W – объем перевозок, обеспечиваемый 1 мин. радиорекламы, а z – общий объем перевозок, то целевая функция может быть записана в виде

.

Так как величина W считается постоянной, вместо функции можно рассматривать функцию

,

максимум, которой в некоторой области достигается в тех же точках, что и функцией .

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

,

а так же с конъюнктурными интересами железной дороги

.

Кроме того, имеются ограничения, связанные с объемом времени на рекламу

; ; .

Таким образом, рассматриваемая задача записывается в виде

 

(2.4)

 

(2.5)

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

 

20х1+60х2=3000

х1-2х2=0

х1=100 (2.6)

х1=0

х2=0

 

 

y=60
x1

Рис. 2.

 

Решение системы неравенств (2.5) образует на плоскости четырехугольник OPRS, а целевая функция при различных значениях у образует на плоскости параллельные прямые (рис. 2.2). При этом значение у возрастет в направлении вектора

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

Уточним координаты точки Р. Для этого учтем, что она является точкой пересечения прямых, описываемых уравнениями

Решив систему, найдем координаты точки Р (60;30). Это означает, что для получения наибольшего объема перевозок необходимо выделить средства на 60 мин. радиорекламы в размере 1200 условных единиц и на 30 мин. телерекламы в размере 1800 условных единиц.

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

 

Симплекс – метод.

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

F = х12 max

х12 -2 х123 = -2

х1-2х2 -13 х1-2х2- х4 = -13

12 6 3х125 = 6

х1 0, х2 0 х1 0, х2 0

а) приведем задачу к каноническому виду;

б) учтем, что х1 и х2 – основные переменные (они входят в целевую функцию), х3, х4 и х5 – неосновные переменные.

Выразим неосновные переменные через основные:

 

 

12-2 = х3

х1-2х2+13 = х4

-3х12+6 = х5

х1 0, х2 0 F = х12

в) составим симплекс – таблицу:

  1 2 b
х3 -1 -2
х4 -1
х5 -1
F -1 -1

 

 

Переменные x1, x2 включаются в таблицу с коэффициентом + для задачи минимизации и с коэффициентом - для задачи максимизации. Если последний столбец и последняя строка не содержат отрицательных чисел, то получен ответ. В противном случае проводится МЖИ (метод модифицированных жордановых исключений) – процедура, с помощью которой избавляются от отрицательных чисел сначала в последнем столбце, затем в последней строке. В последнем столбце выбираем любой отрицательный элемент (например: -2) и движемся по строке, в которой он расположен. Берем любой отрицательный элемент в этой строке (например: -1), который расположен во втором столбце (разрешающийстолбец). Далее поэлементно делим последний столбец на разрешающий столбец. Из положительных полученных отношений берем наименьшее (min = 2). Строка, в которой достигается минимум, называется разрешающей. Элемент, расположенный на пересечении разрешающей строки и разрешающего столбца, называется разрешающим (-1);

г) преобразуем таблицу. Для этого

а) в разрешающей строке и разрешающем столбце переменные меняем местами (т.е. х2 и х3);

 

 

1 3 b
х2 -1 -1
х4
х5 -1
F -2 -1

 

 

б) на месте разрешающего элемента (-1) пишем 1/ разрешающий элемент (1:(-1) = -1);

в) в разрешающей строке каждое число (кроме (-1)) делим на разрешающий элемент;

г) в разрешающем столбце каждое число (кроме (-1)) делим на разрешающий элемент и результат берем со знаком минус;

д) остальные элементы считаем по правилу прямоугольников:

старый элемент разрешающий элемент -

новый элемент = ----------------------------------------------------------------,

разрешающий элемент

 

старый элемент

 

 

разрешающий элемент

 

 

- элемент разрешающей строки (в одном столбце со старым),

- элемент разрешающего столбца (в одной строке со старым).

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

ж) в разрешающей строке и разрешающем столбце переменные меняем местами (т.е. х1 и х5); повторяем расчеты;

 

 

  5 3 b
х2 0,5 -1,5
х4 -0,5 2,5
х1 0,5 -0,5
F -2

 

 

з) снова повторяем расчеты:

 

  5 4 b
х2   0,6
х3 -0,2 0,4
х1   0,2
F 0,6 0,8

 

Последний столбец и последняя строка не содержат отрицательных чисел задача решена:

 

х1 = 5, х2 = 9, х3 = 2 F = 14 – 0,6 *х5 – 0,8*х4,

Fmax=14, Х=( х1, х2, х3, х4, х5) = (5,9,2,0,0).

 

Ответ: Fmax=14, х1 = 5, х2 = 9.

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