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

Рассмотрим построение математической модели и решение оптимизационной задачи ЛП.

Небольшая фабрика изготовляет два вида красок: для внутренних (I) и наружных (Е) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта – А и В. максимально возможные суточные запасы этих продуктов составляют 6 и 8т соответственно. Расходы А и В на 1т соответствующих красок приведены в таблице.

Исходный продукт	Расход исходных продуктов ( в тоннах) на тонну краски		Максимально возможный запас, т
	Краска Е	Краска I
А	1	2	6
В	2	1	8

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1т. Кроме того, установлено, что спрос на краску I никогда не превышает 2т в сутки.

Оптовые цены одной тонны красок равны: 3 у.е. для краски Е, 2 у.е. для краски I.

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

Построение математической модели

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

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

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

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

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

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

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

Переменные. Так как нужно определить объемы производства каждого вида краски, переменными в модели являются

Хе – суточный объем производства краски Е (в тоннах),

Х i – суточный объем производства краски I (в тоннах).

Целевая функция. Так как стоимость 1т краски Е равно 3 у.е., суточный доход от ее продажи составит 3 Хе у.е. Аналогично доход от реализации Х i тонн краски I составит 2 Х i у.е. в сутки. При допущении независимости объемов сбыта каждой из красок общий доход равен сумме двух слагаемых – дохода от продажи краски Е и дохода от продажи краски I.

Обозначив общий доход ( в у.е.) через z, можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения x_e и x_i, , максимизирующие величину общего дохода z = 3 x_e + 2 x_i

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

Расход исходного продукта Максимально возможный

для производства обоих  запас данного исходного

видов краски продукта

Это приводит к следующим двум ограничениям:

x + 2x_i  6 (для А)

2x + x_i  8 (для В)

Ограничения на величину спроса на продукцию имеют вид:

Превышение спроса на

краску I относительно  1 тонна/ сутки,

спроса на краску Е

( Спрос на краску I )  2 тонны/ сутки.

Математически эти ограничения записываются следующим образом

x_i - x_е  1 (соотношение величин спроса на краску I и краску Е)

x_i  2 (максимальная величина спроса на краску I ).

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

x_i  0 ( объем производства краски I),

x_е  0 ( объем производства краски Е).

Итак, математическую модель можно записать следующим образом.

Определить суточные объемы производства x_i и x_е краски I и краски Е (в тоннах), при которых достигается

Max Z= 3x_е + 2 x_i (целевая функция)

при ограничениях x_е + 2 x_i  6

2x_е + x_i  8

-x_е + x_i  1 ограничения

x_i  2

x_i  0 , x_е  0

Что определяет линейный характер построенной модели? С формальных позиций данная модель является линейной потому, что все входящие в нее функции ( ограничения и целевая функция) линейны. Линейность предполагает наличие двух свойств – пропорциональности и аддитивности.

1. Пропорциональность означает, что вклад каждой переменной (т.е. x_i и x_е) в целевую функцию и общий объем потребления соответствующих ресурсов прямо пропорционален уровню (величине) этой переменной.

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

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

Максимизировать z= C₁x₁ + C₂x₂ + . . . +C_nx_n

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

а₁₁х₁ +а₁₂х₂+ . . . +а_1nx_nb₁

а₂₁х₁ +а₂₂х₂+ . . . +а_2nx_nb₂

. . . . . . . . . . . . . . . . . . . . . . .

а_m1х₁ +а_m2х₂+ . . . +а_mnx_nb_m

x₁, x₂, . . . , x_n 0

Модель ЛП на правлена на поиск наиболее выгодного способа распределения ограниченных ресурсов по нескольким видам производственной деятельности. В сформулированной выше задаче непосредственно n видов производственной деятельности, интенсивности использования которых ( искомые величины) равны x₁, x₂, . . . , x_n . Для осуществления всех видов производственной деятельности имеется m видов ресурсов, возможные объемы потребления которых ограничены значениями b₁,

b₂ ,. . . , b_m. Расход i-го ресурса на единицу продукции j-го вида производства равен а_ij . Поэтому сумма ⁿ_j=1a_ijx_j , представляющая собой общий объем ресурса i , потребляемый n видами производства, не может превышать величины b_i.

Структура целевой функции ⁿ_j=1C_jx_j C_j отражает вклад каждого вида производственной деятельности в общий результат. В случае максимизации C_j представляет собой прибыль от j-го вида производственной деятельности на единицу соответствующей продукции, а в случае минимизации C_j характеризует удельные затраты. Заметим, что «полезность» некоторого вида производственной деятельности нельзя установить только по значению соответствующего коэффициента целевой функции, так как объем потребления ограниченных ресурсов также является важным фактором. Поскольку все виды производственной деятельности, представленные в модели, претендуют на использование ограниченных ресурсов, относительная полезность некоторого вида производства ( по сравнению с другими видами производственной деятельности) зависит как от потребления ресурсов a_ij . Поэтому может оказаться, что из – за слишком большого расхода ограниченных ресурсов некоторый i- й вид производственной деятельности, характеризующийся высокой прибылью, использовать нецелесообразно ( т.е. в оптимальном решении x_j=0).

Лекция 4: