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

 

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

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

 

Основные понятия и теоремы линейного программирования

 

Рассмотрим каноническую задачу линейного программирования. Перепишем её в векторной форме: найти минимум функции L = CX при условиях

                

A 1 x 1 + A 2 x 2 +…+ Anxn = B,

(5.4)

                                      

где C =(с ₁ ;с ₂ ;…;с _n), X =(х ₁ ;х ₂ ;…;х _n); CX – скалярное произведение векторов; А ₁ ,…,А _n и В – m -мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи:

.

Определение 5.1. План X =(х ₁ ;х ₂ ;…х _n) называется опорным планом канонической задачи линейного программирования, если система векторов A_j, входящих в разложение (5.4) с положительными коэффициентами, линейно независима.

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

Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае он называется вырожденным.

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

Теорема 5.1. Множество планов канонической задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов канонической задачи линейного программирования называется многогранником решений, а всякая угловая точка многогранника решений – вершиной.

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

Теорема 5.3. Если система векторов А ₁ ,А ₂ ,…,А _k (k ≤ n) в разложении (5.4) линейно независима и такова, что А ₁ х ₁ +А ₂ х ₂ +…+А _k x_k = B, где все x_j ≥0, то точка X =(х ₁ ;х ₂ ;…;х _k; 0;…;0 ) является вершиной многогранника решений.

Теорема 5.4. Если X = (х ₁ ;х ₂ ;…х _n) – вершина многогранника решений, то вектора A_j, соответствующие положительным x_j в разложении (5.4), линейно независимы.

Сформулированные теоремы позволяют сделать следующие выводы.

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

Вершину многогранника решений, в которой целевая функция принимает экстремальное значение, найти сравнительно просто, если задача, записанная в форме стандартной, содержит не более 2-х переменных или задача, записанная в форме канонической, содержит не более 2-х свободных переменных, т.е. n - r ≤2, где n – число переменных, r – ранг матрицы, составленной из коэффициентов в системе ограничений задачи.