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

В ППП Матлаб решение задач линейного программирования после предс-тавления соответствующих матриц осуществляется вызовом оператора

x = linprog (f, A, b, Aeq, beq, lb, ub) (10.18)

или

[x, fval] = linprog (f, A, b, Aeq, beq, lb, ub) , (10.19)

где: x- выходной вектор оптимальных иcкомых переменных ;

fval- оптимальное значение целевой функции;

f- вектор коэффициентов целевой функции,;

A- матрица коэффициентов левой части уравнений ограничений;

b- вектор коэффициентов правой части уравнений ограничений;

Aeq- матрица коэффициентов левой части уравнений равенств;

beq- вектор коэффициентов правой части уравнений равенств;

lb- вектор нижнего порога ограничений искомых переменных;

ub- вектор верхнего порога ограничений искомых переменных.

Оператор linprog минимизирует функцию

minx f^T x

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

Ax <= b;

A_eq = beq ;

lb <= x <= ub

и выдает решение в виде вектора оптимальных значений переменных x и оптимального значения целевой функции f_val = min f.

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

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

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

10.4.1. Оптимизации количества удобрений, вносимых в поле

Постановка задачи. Агроному необходимо определить количество органи-ческих и сложных минеральных удобрений для разбрасывания на 20 га лугопас-тбищных угодий таким образом, чтобы полная стоимость вносимых удобрений была минимальной. Стоимость и химический состав последних показаны ниже в таблице 10.2.

Таблица 10.2. Стоимость и химический состав удобрений

(данные имеют относительный характер)

Удобрение	Стоимость, руб/т	Азот, кг/т кг/т	Фосфор, кг/т	Калий, кг/т
Органическое удобрение	125	6	1.5	4
Сложное удобрение	6500	250	100	100

Предполагается внести на луг не менее 75 кг/га азота, 25 кг/га фосфора и 35 кг/га калия. Производительность труда при разбрасывании органического удобре-ния может составлять 8 т/ч, а сложного удобрения — 0,4 т/ч при ресурсах времени для выполнения этой работы 25 ч.

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

- управляемые переменные,

- целевую функцию,

- ограничения на значения управляемых переменных.

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

1.Управляемые переменные.

Задача агронома — определить количество органического и сложного удоб-рения. Поэтому названные величины и должны выступать в роли управляемых переменных.

Пусть:

х₁ = количество разбрасываемого органического удобрения, т;

x₂ = количество вносимого сложного удобрения, т.

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

2.Целевая функция.

Цель агронома — свести к минимуму полную стоимость вносимых удоб-рений. Органическое удобрение обходится ему по 125 руб., а сложное удобрение — по 6500 руб. за 1 т, так что полная стоимость может быть задана в виде

125* х₁ + 6500* x₂ .

Обозначив ее через F, можем записать целевую функцию:

минимизировать F = 125* х₁ + 6500* x₂ . (10.20)

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

min F → max( - F).

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

максимизировать ( - F) = - 125* х₁ - 6500* x₂.

3. Ограничения.

Ограничения на значения переменных накладываются, во-первых, соображе-ниями агронома о минимальных нормах внесения азота (75 кг/га), фосфора (25 кг/га) и калия (35 кг/га) и, во-вторых, ресурсом времени (25 ч), выделенным на выполнение всех работ. Рассмотрим сначала ограничение на нормы внесения азота.

В 1 т органического удобрения содержится 6 кг, а в 1 т комбинированных удобрений — 250 кг азота, то есть всего в органическом удобрении содержится 6х₁ кг, а в комбинированных удобрениях 250x₂ кг азота. Таким образом, общее количество азота, вносимого на угодья, составляет

6* х₁ + 250* x₂

и это суммарное количество не должно быть меньше 1500 кг, так как минимальная норма внесения — 75 кг/га, а площадь угодий — 20 га.

Поэтому ограничения по азоту можно записать в виде

6* х₁ + 250* x₂ >=1500. (10.21)

Подобным образом строятся ограничения по фосфору

1.5* х₁ + 100* x₂ >= 500 (10.22) и калию

4* х₁ + 100* x₂ >= 700. (10.23) И, наконец, ограничение по ресурсу времени. Агроном разбрасывает органические удобрения с производительностью 8 т/ч и вносит сложные химические удобрение с производительностью 0,4 т/ч. Общее время, необходимое для выполнения этой работы, составляет х₁ /8 + x₂/0.4 и не должно превышать

0.125*х₁ + 0.25*x₂ <= 25;

1* х₁ + 200*x₂ <= 200. (10.24)

В формализациях задач линейного программирования константы, фи-гурирующие в ограничениях, обычно записываются в правой части соответст-вующих неравенств (уравнений). В этой роли могут выступать только неотрицате-льные, числа. Любую отрицательную константу можно заменить на положи-тельную путем умножения обеих частей ограничения на - 1 и замены (в случае, если ограничение задано неравенством) знака неравенства на противоположный (например, знак < должен быть заменен на знак <, и наоборот). В нашем примере константы представлены числами 1500, 500, 700 и 200 (см. неравенства 10.21, …, 10.23).

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

4. Специальные требования.

Целевая функция и ограничения в рассматриваемом примере линейна, так как уравнение (10.22) и неравенства (10.21, ..., 10.24) не содержат членов, в которые входили бы переменные в степени выше 1 либо произведения переменных. Они детерминированы, так как коэффициенты при переменных управления, как в целевой функции, так и в ограничениях — постоянные величины.

Переменные управления х₁ и x₂ не могут принимать отрицательных значе-ний, поскольку внесение отрицательного количества удобрения было бы лишено физического смысла. Это значит, что выполняется условие неотрицательности, то есть

х₁ >= 0;

x₂ >= 0. (10.25)

И, наконец, х₁ и x₂ , удовлетворяя требованиям наложенных на них ограни-чений, могут принимать любые значения. Это значит, что выполняется условие непрерывности.

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

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

Минимизировать F = 125* х₁ + 6500* x₂ (целевая функция) (10.26)

с учетом:

6* х₁ + 250* x₂ >=1500 (ограничение пo азоту); (10.27)

1.5* х₁ + 100* x₂ >= 500 (ограничение по фосфору); (10.28)

4* х₁ + 100* x₂ >= 700 (ограничение по калию); (10.29) 1* х₁ + 200*x₂ <= 200 (ограничение по времени); (10.30)

1* х₁ >= 0 (условие неотрицательности); (10.31)

1*x₂ >= 0 (условие неотрицательности). (10.32)

Пример решения данной задачи с помощью функции linprog пакета приклад-ных программ Matlab приведен ниже. Прежде всего необходимо обратить внима-ние, что эта функция работает в режиме минимизации с ограничением снизу (<=). Для этого в ограничениях (10.26,… ,10.32) меняются знаки коэффициентов правой и левой частей и вид ограничений на обратные. После этого составляются исход-ные матрицы и вектора целевой функции и ограничений. Матрица целевой функ-ции, определяемая ценами на удобрения:

f = [125; 6500].

Матрица коэффициентов левой части ограничений:

A = [-6 -250

-1.5 -100

-4 -100

-1 -200 ]

и вектор правой части ограничений:

b = [-1500; -500; -700; -200].

Условия неотрицательности переменных х₁ и x₂ записываются нулями в векторе

lb = zeros(2,1).

После ввода полученных матриц и векторов в оператор линейного програм-мирования

[x,fval] = linprog(f,A,b,lb)

получается решение в виде вектора искомых переменных

x = [ 19.1111; 3.3333]

обеспечивающих минимум целевой функции

fval = 35556.

Интерпретируется результат следующим образом:

для достижения минимальной цены удобрений f = 35556 руб. необходимо внести:

органических удобрений х₁ = 19.1 т;

сложных удобрений x₂ = 3.3 т.