Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

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

Большинство задач, решаемых методами исследования операций, может быть сформулировано так:

максимизировать F(x1, x2, ., xn) при ограничениях$$ g_1 (x_1 , . , x_n) \leq b_1 ; \\ g_2 (x_1 , . , x_n) \leq b_2 ; \\ . \quad . \quad . \quad . \quad . \quad . \quad . \quad \\ g_m (x_1 , . , x_n) \leq b_m $$, где f(x1, x2, ., xn) - целевая функция, или критерий эффективности (например, прибыль от производства каких-либо видов продукции, стоимость перевозок и т.п.); X={x1,.,xn} - варьируемые параметры; g1(x),.,gm(x) - функции, которые задают ограничения на имеющиеся ресурсы.

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

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

Рассмотрим некоторые из них.

Определение оптимального ассортимента. Имеются m видов ресурсов в количествах b1, b2, . , bi, bm и n видов изделий. Задана матрица A=||aij||, i=1 ,.,m, j=1,.,n, где aij характеризует нормы расхода i -го ресурса на единицу j -го вида изделий. Эффективность производства j -го вида изделий характеризуется показателем Cj, удовлетворяющим условию линейности. Нужно определить такой план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности будет наибольший.

Обозначим количество единиц k -го вида изделий, выпускаемых предприятием, через xk, $$k = \overline{1, K}$$. Тогда математическая модель этой задачи будет иметь такой вид:$$\text{максимизировать} \; \sum_k c_k x_k$$ при ограничениях$$ \sum_k a_{ik} x_k \leq b_i , \quad i = 1, 2, . , m$$

Кроме ограничений на ресурсы (3.2) в эту модель можно ввести дополнительные ограничения на планируемый уровень выпуска продукции $$x_j \geq x_{j0}$$, xi : xj : xk = bi : bj : bk для всех i, j, k и т.д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются m видов взаимозаменяемых ресурсов а1, а2, ., аm, используемых при выполнении n различных работ (задач). Объемы работ, которые должны быть выполнены, составляют b1, b2, . , bi, bn единиц. Заданы числа $$\lambda_{ij}$$, указывающие, сколько единиц j -й работы можно получить из единицы і -го ресурса, а также Cij - затраты на производство j -й работы из единицы i -го ресурса. Требуется распределить ресурсы по работам таким образом, чтобы суммарная эффективность выполненных работ была максимальной (или суммарные затраты - минимальными).

Данная задача называется общей распределительной задачей. Количество единиц i -го ресурса, которое выделено на выполнение работ j -го вида, обозначим через xij.

Математическая модель рассматриваемой задачи такова:$$\text{минимизировать} \; \sum_{j=1}^n \sum_{i=1}^m c_{ij} x_{ij}$$ при ограничениях$$\sum_{i=1}^m \lambda_{ij} x_{ij} \geq b_j, \quad j = 1, 2, ., n ,$$ $$\sum_{j=1}^n x_{ij} = a_i, \quad i=1,2,.,m.$$

Ограничение (3.4) означает, что план всех работ должен быть выполнен полностью, а (3.5) означает, что ресурсы должны быть израсходованы целиком.

Примером этой задачи может быть задача о распределении самолетов по авиалиниям.

Задача о смесях. Имеется р компонентов, при сочетании которых в разных пропорциях получают разные смеси. Каждый компонент, а следовательно и смесь, содержит q веществ. Количество k -го вещества k = 1, 2, ., q, входящее в состав единицы і -го компонента и в состав единицы смеси, обозначим через аik и аk соответственно.

Предположим, что аk зависит от аik линейно, то есть если смесь состоит из x1 единиц первого компонента, x2 - единицу второго компонента и т.д., то$$a_k = \sum_i a_{ik} x_i .$$

Задано р величин Ci, характеризующих стоимость, массу или калорийность единицы i -го компонента, и q величин bk, указывающих минимально необходимое процентное содержание k -го вещества в смеси. Обозначим через x1, x2,.,xр значение компонента р -го вида, входящего в состав смеси.

Математическая модель этой задачи имеет такой вид:$$\text{минимизировать} \; \sum_{i=1}^p c_i x_i$$ при ограничении$$\sum_{i=1}^p a_{ik} x_i \geq b_k , \quad k=1,2,.,q ,$$ $$\sum_{i=1}^p x_i =1$$

Ограничение (3.7) означает, что процентное содержание k -го вещества в единице смеси должно быть не меньше bk.

К этой же модели принадлежит также задача определения оптимального рациона кормления скота.

Задача о раскрое материалов. Пусть поступает в раскрой m различных материалов. Требуется изготовить из них k разных комплектующих изделий (комплектов) в количествах, пропорциональных величинам b1, b2, . , bk (условия комплектности). Пусть каждую единицу j -го материала j=1, ., m можно раскроить n различными способами, так что при использовании i -го способа раскроя, i=1, ., n получим аij единиц k -го изделия. Нужно определить такой план раскроя материалов, обеспечивающий максимальное количество комплектов, если имеющийся запас j -го материала составляет аj единиц.

Обозначим через xij количество единиц j -го материала, раскраиваемых i -м способом, а через x -общее количество изготавливаемых комплектов.

Математическая модель этой задачи имеет такой вид:$$\text{максимизировать} \; x$$ при условиях$$\sum_{i=1}^n x_{ij} \leq a_j,$$ $$\sum_{j=1}^m x_{ij} a_{ij}^{(k)} = b_k x, \quad k=\overline{1, K}$$

Условие (3.9) означает ограничение на запас j -го материала, а (3.10) - условие комплектности.

Оптимальные балансовые модели. Рассмотрим n -отраслевую балансовую модель с постоянными технологическими коэффициентами, задаваемыми матрицей затрат A=||aij||, где aij затраты продуктов i -й отрасли на производство единицы продукции j -й отрасли. Производственные мощности i -й отрасли ограничивают ее валовой выпуск величиной di (i = 1, ...,n), и пусть цена конечного продукта i -й отрасли составляет ci единиц.

Нужно определить оптимальный валовой выпуск продукции каждой отрасли, при котором будет достигнут максимальный суммарный выпуск конечного продукта в денежном выражении.

Обозначим вектор валовой продукции всех отраслей через x=[x1,.,xn], а вектор конечного продукта y=[y1,.,yn]. Тогда yi - объем продукции i -й отрасли, идущего на накопление.

Между векторами x и y существует следующая связь:

x = Ax+y,

где Ax - продукт, расходуемый на потребление. Отсюда

y=x [E-А], x=[E-A]-1y

Математическая модель этой задачи имеет вид

максимизировать cTy

при условиях$$x=[E-A]^{-1}y \leq d , \; y \geq 0;$$

Кроме того, в этой задаче можно дополнительно использовать такие, например, ограничения на конечные продукты:

а) y1:y2:.:yn=b1:b2:.:bn -условие комплектности;

б) $$d_i \geq y_i \geq b_i$$ - условие ограниченности выпуска конечного продукта.

Форма записи задачи ЛП. Задачу линейного программирования можно сформулировать так:$$\text{максимизировать} \; \sum_{i=1}^n c_i x_i$$ при условиях$$ a_{11}x_1 + a_{12}x_2+ . +a_{1n}x_n \leq b_1 ; \\ a_{21}x_1 + a_{22}x_2+ . +a_{2n}x_n \leq b_2 ; \\ . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad \\ a_{m1}x_1 + a_{m2}x_2+ . +a_{mn}x_n \leq b_m ;$$ $$x_1 \geq 0, x_2 \geq 0, ., x_n \geq 0,$$

Ограничения (3.13) называют условиями неотрицательности переменных. В рассматриваемом случае все ограничения имеют вид неравенств.

Иногда они могут быть смешанными, то есть неравенства и равенства:$$ a_{11}x_1 + a_{12}x_2+ . +a_{1n}x_n \leq b_1 ; \\ a_{21}x_1 + a_{22}x_2+ . +a_{2n}x_n \leq b_2 ; \\ . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad \\ a_{m1}x_1 + a_{m2}x_2+ . +a_{mn}x_n \leq b_m ; \\ a_{m+1,1}x_1 + a_{m+1,2}x_2+ . +a_{m+1,n}x_n = b_{m+1} ; \\ a_{k1}x_1 + a_{k2}x_2+ . +a_{kn}x_n = b_k$$ Если все ограничения задачи ЛП имеют вид строгих равенств$$ a_{11}x_1 + a_{12}x_2+ . +a_{1n}x_n = b_1 ; \\ a_{21}x_1 + a_{22}x_2+ . +a_{2n}x_n = b_2 ; \\ . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad . \quad \\ a_{m1}x_1 + a_{m2}x_2+ . +a_{mn}x_n = b_m ;$$ то данная форма записи называется канонической.

В матричной форме задача ЛП записывается следующим образом:$$\text{максимизировать} \; c^T x$$ при ограничениях$$Ax \leq b; x \geq 0 ,$$ где А - матрица ограничений размером ( m x n ); b(m*1) - вектор-столбец свободных членов; x(n*1) - вектор переменных; с=[c1, c2,.,cn] -вектор (строка) коэффициентов целевой функции.

В векторной форме ограничения (3.14) записывают так:$$A_1 x_1 + A_2 x_2 + . + A-n x_n \leq b ,$$

Допустимым множеством решений задачи (3.11)-(3.13) называется множество R(х) всех векторов x, удовлетворяющих условиям (3.12) и (3.13).

Множество R(х) представляет собой выпуклое многогранное множество или выпуклый многогранник.

Решение x0 называется оптимальным, если оно удовлетворяет условию$$c^T x_0 \ge c^T x,$$ для всех $$x \in R (х)$$.

Поскольку поиск $$\min f(х)$$ эквивалентен поиску $$\mах [-f(х)]$$, то задачу ЛП всегда можно свести к эквивалентной задаче максимизации.

4. Решение задач линейного программирования симплекс–методом

Симплекс-метод, известный также под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.

Алгоритмы симплекс-метода позволяют также установить, является ли задача ЛП разрешимой.

Запишем ограничения задачи ЛП в таком виде:

A1x1 + A2x2 + ... + Anxn + An+1xn+1 + ... + An+mxn+m = A0.

Пусть A1,...,Am - множество линейно независимых векторов.

Тогда уравнение$$A_1 x_1^* + A_2 x_2^* + \ldots + A_n x_n^* + A_{n+1} x_{n+1}^* + \ldots + A_{n+m} x_{n+m}^* = A_0$$ определяет базисное решение $$x_1^*, x_2^*, \ldots ,x_m^*$$,

Предположим, что это решение допустимо, то есть $$x_1^* \geq 0, x_2^* \geq 0, ., x_m^* \geq 0$$. Базис {A1,.,Am} образует m -мерное пространство, а потому каждый из векторов Am+1,.,Am+n единственным образом выражается через этот базис. Если Ar не входит в базис, то$$A_1 x_{1r} + A_2 x_{2r} + \ldots + A_m x_{mr} = A_r,$$ где xir - соответствующие коэффициенты (i = 1, 2, ..., m).

Предположим, что хотя бы одна из величин xir больше нуля.

Решение уравнения$$A_1 x_1 + A_2 x_2 + \ldots + A_m x_m + A_r x_r = A_0$$ обозначим как $$\{ \widetilde{x}_1 , \widetilde{x}_2 , \ldots , \widetilde{x}_m , \widetilde{x}_r \}$$

Тогда, очевидно:$$A_1 \widetilde{x}_1 + A_2 \widetilde{x}_2 + \ldots + A_m \widetilde{x}_m + A_r \widetilde{x}_r =A_0 .$$

Умножив уравнение (4.2) на xr и вычтя полученное уравнение из уравнения (4.1), получим$$A_1 (x_1^* - x_r x_{1r}) + A_2 (x_2^* - x_r x_{2r}) + \ldots + A_m (x_m^* - x_r x_{mr}) = A_0 - x_r A_r .$$

Сравнив уравнения (4.5) и (4.4), находим связь нового решения $$\widetilde{x}_1, ., \widetilde{x}_m, x_r$$ со старым базисным решением $$x^*_1, ., x^*_m$$:$$\widetilde{x}_1 = x_1^* - x_r, \, \widetilde{x}_2 = x_2^* - x_r x_{2r} , \, \ldots , \, \widetilde{x}_m = x_m^* - x_r x_{mr} , \, x_r .$$

Решение (4.6), во-первых, не будет базисным, так как содержит m + 1 переменную, а во-вторых, будет допустимым не для всех значений xr.

Чтобы новое решение оставалось допустимым, нужно выбрать значение xr таким, чтобы ни одна из величин $$\widetilde{x}_i = x_i^* - x_r x_{ir} \quad (i=1, 2, \ldots, m)$$ не стала меньше нуля. Следовательно, максимальное значение переменной xr определяется соотношением$$x_{r \max} = \min_i \left\{ \frac{x_i^*}{x_{ir}} \right\} ,$$ где xir > 0.

Чтобы сделать новое допустимое решение базисным, нужно одну переменную xi вывести из базисного решения, а соответствующий вектор из базиса. В этом случае новый базис будет содержать также m векторов.

Для этого выбираем значения в соответствии с (4.7). Тогда новое базисное решение имеет вид$$ x_1^* - x_{r \max} x_{1r} ; \\ x_2^* - x_{r \max} x_{2r} ; \\ x_j \; \text{(опущен)} \\ x_{r \max}$$, а новый базис - (A1, A2, ., Aj-1, Aj+1, ., Am, Ar).

Такой переход от одного базиса к другому позволяет находить решения почти всех задач ЛП. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений m и n это практически невозможно. Поэтому для перехода от текущего решения к новому допустимому базисному решению, которому отвечает большее значение целевой функции, используют соответствующий критерий ( симплекс-разность ).

Новому ДБР $$x_1^* - x_r x_{1r}, x_2^* - x_r x_{2r}, . , x_m^* - x_r x_mr, x_r$$ соответствует следующее значение целевой функции$$z_1 = c_1(x_1^* - x_r x_{1r}) + c_2(x_2^* - x_r x_{2r}) + . + c_r x_r = \\ = (c_1 x_1^* + c_2x_2^* + \ldots + c_m x_m^*) + x_r (c_r - c_{1r} - \ldots - c_mx_{mr}) = \\ = z_0 + x_r (c_r - c_1 x_{1r} - \ldots - c_m x_mr)$$, где z0 - значение целевой функции для начального ДБР;

сr-с1x1r - с2x2r - ... - сmxmr - симплекс-разность для переменной хr.

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

Таким образом, алгоритм симплекс-метода состоит из следующих этапов:

Этапы 2 - 4 повторяют до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными.

Это и есть признак оптимальности текущего базисного решения.