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

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

Пусть выпускается 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_nx_n

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

,

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

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

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

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

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

.

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

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

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

a_i1x₁+a_i2x₂+…+a_inx_n≤b_i

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

a_i1x₁+a_i2x₂+…+a_inx_n+x_n+1=b_i (x_n+1≥0),

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

a_i1x₁+a_i2x₂+…+a_inx_n≥b_i

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

a_i1x₁+a_i2x₂+…+a_inx_n-x_n+1=b_i (x_n+1≥0).

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

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

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

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