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

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

Пусть выпускается n видов продукции, используется m видов сырья. Обозначим через S_i (i= 1, …,m) виды сырья; b_i – запасы сырья i -го вида; P_j (j= 1, …,n) – виды продукции; a_ij – количество единиц i -го сырья, идущего на изготовление единицы j -й продукции; с_i – величину прибыли, получаемой при реализации единицы j -й продукции.

Условия задачи запишем в таблице 4.2.

Пусть x_ij – количество единиц j -й продукции, которое необходимо произвести. Сама модель:

найти максимальное значение линейной функции

Z=c ₁ x ₁ + +c ₂ x ₂ +…+c _n x _n

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

,

где a_ij – количество сырья, расходуемое на изготовление единицы продукции, b_i – общее количество сырья i -го вида, c_j – величина прибыли, получаемой с единицы j -й продукции.

Система ограничений и функция цели составляют математическую модель рассматриваемой экономической задачи.

Как мы уже выясняли, допустимым решением (или планом) задачи линейного программирования является совокупность чисел х=(х ₁ ,х ₂ ,…,х_n), удовлетворяющих ограничениям задачи. План х^*=(х ₁ ^*,х ₂ ^*,…,х_n^*), при котором целевая функция задачи принимает своё максимальное (минимальное) значение, называется оптимальным.

Таблица 5.2 – Условия задачи оптимального использования комплексного сырья

Виды	Запасы	Количество единиц i -го сырья, идущего на изготовление единицы j -й продукции
сырья	сырья	P 1	P 2	...	Pn
S 1	b 1	a 11	a 12	...	a 1 n
S 2	b 2	a 21	a 22	...	a 2 n
...	...	...	...	...	...
Sm	bm	am 1	am 2	...	amn
Прибыль	с 1	с 2	...	сn

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

.

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

В том случае, когда требуется найти функцию L = c ₁ x ₁ +c ₂ x ₂ +…+c_nx_n, можно перейти к нахождению максимума функции L ₁ = -L= -c ₁ x ₁ -c ₂ x ₂ -… -c_nx_n, поскольку min L ₁ = - max (-L).

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

a_{i 1} x ₁ +a_{i 2} x ₂ +…+a_inx_n≤b_i

преобразуется в ограничение-равенство

a_{i 1} x ₁ +a_{i 2} x ₂ +…+a_inx_n+x_{n +1} =b_i (x_{n +1}≥0),

а ограничение-неравенство

a_{i 1} x ₁ +a_{i 2} x ₂ +…+a_inx_n≥b_i

в ограничение-равенство

a_{i 1} x ₁ +a_{i 2} x ₂ +…+a_inx_n-x_{n +1} =b_i (x_{n +1}≥0).

В то же время каждое уравнение системы ограничений может быть представлено так:

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

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

Отметим, наконец, что если переменная х_k не подчинена условию неотрицательности, то её следует заменить двумя неотрицательными переменными u_k и v_k, приняв x_k=u_k-v_k.