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

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

Пусть имеется m ресурсов, каждый i-й ресурс – в количестве b_i ( ). Эти ресурсы необходимо использовать для n видов продукции. Для выпуска единицы j-го вида продукции необходимо a_ij единиц i-го вида ресурса. Требуется определить, какое количество каждой номенклатуры продукции следует произвести, чтобы такой выпуск был наилучшим для принятого критерия оптимальности. Отсюда следует, что

( ), (1)

где x_j – количество выпускаемого j-го вида продукции.

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

d_j  x_j  D_j ( ),

где d_j, D_j – соответственно минимальное и максимальное предельно допустимое количество выпускаемой продукции j-го вида.

В зависимость (1) введем дополнительные переменные y_i  0. Запишем

+ y_i = b_i ( ). (2)

В реальных задачах суммарное количество основных x_j ( ) и дополнительных y_i ( ) переменных всегда больше, чем число зависимостей m, поэтому система (2) имеет множество решений. Ресурсы всегда используются для получения некоторого результата. Поэтому в задачах распределения ресурсов возможна только одна из двух взаимно исключающих постановок: при заданных ресурсах максимизировать получаемый результат; при заданном результате минимизировать потребные ресурсы. Математическая модель первой постановки

Е =  max;  b_i ( ); d_j  x_j  D_j ( ),

где c_j – величина, показывающая, какой вклад в результат дает единица выпускаемой продукции x_i.

При решении задачи определяются такие значения x_j, которые обеспечивают получение при заданных ресурсах максимального результата.

Вторая постановка задачи распределения ресурсов имеет вид:

Е =  min;  R_зад; d_j  x_j  D_j ( ),

где R_зад – минимально допустимое значение требуемого результата.

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

2. Формулировка задачи и метод ее решения

2.1. Симплекс-метод решения задач

линейного программирования (ЛП)

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

Е =  max (min);  b_i ( ); x_j  0 ( ).

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

Этапы решения задачи ЛП на основе симплекс-метода.

Этап 1. Представить исходные данные задачи в виде симплекс-таблицы. Задана следующая задача ЛП:

E = c₀ + c₁x₁ + c₂x₂ + c₃x₃  max (min); a₁₁x₁ + a₁₂x₂ + a₁₃x₃  b₁;

a₂₁x₁ + a₂₂x₂ + a₂₃x₃  b₂; a₃₁x₁ + a₃₂x₂ + a₃₃x₃  b₃;

a₄₁x₁ + a₄₂x₂ + a₄₃x₃  b₄; x_j  0 ( ).

Для записи задачи в виде симплекс таблицы вводим дополнительные переменные в ограничения:

E = c₀ + c₁x₁ + c₂x₂ + c₃x₃  max(min); a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + у₁=b₁;

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + у₂ = b₂; a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + у₃ = b₃;

a₄₁x₁ + a₄₂x₂ + a₄₃x₃ + у₄ = b₄.

Запись задачи в стандартной форме:

E = c₀ – (–c₁x₁ – c₂x₂ – c₃x₃) max(min); у₁=b₁–(a₁₁x₁+a₁₂x₂+a₁₃x₃);

у₂ = b₂ – (a₂₁x₁ + a₂₂x₂ + a₂₃x₃); у₃ = b₃ – (a₃₁x₁ + a₃₂x₂ + a₃₃x₃);

у₄ = b₄ – (a₄₁x₁ + a₄₂x₂ + a₄₃x₃).

Переменные, находящиеся в каждой строке слева, называются базисными, а стоящие в скобках, – свободными. В симплекс-таблицу (табл. 1) заносятся коэффициенты при переменных стандартной формы записи задачи ЛП.

Таблица 1

	Свободный член	x1	x2	x3
E	c0	– c1	– c2	– c3
y1	b1	a11	a12	a13
y2	b2	a21	a22	a23
y3	b3	a31	a32	a33
y4	b4	a41	a42	a43

Пример. Требуется решить задачу:

Е = –2х₁ – 2х₂ + х₃  min(max);

х₁ + х₂ – х₃  – 10; 2х₁ – х₂–5х₃ 5; х₁ – х₂  10; 2х₁ + х₂ + 4х₃  6;

х_j  0 ( ).

Предварительно записываем систему так, чтобы в ограничениях были знаки «», и вводим дополнительные переменные:

Е = –2х₁ – 2х₂ + х₃  min;

– х₁ – х₂ + х₃ + у₁ = 10; – 2х₁ +х₂+5х₃+у₂=–5; х₁ – х₂ + у₃ = 10;

2х₁ + х₂ + 4х₃ + у₄ = 6; х_j  0 ( ); у_i  0 ( ).

Запишем задачу в стандартной форме:

Е = 0 – (2х₁ + 2х₂ – х₃) min;

у₁ = 10 – (– х₁ – х₂ + х₃); у₂ = – 5 – (– 2х₁ + х₂+ 5х₃);

у₃ = 10 – (х₁ – х₂); у₄ = 6 – (2х₁ + х₂ + 4х₃).

Составим симплекс-таблицу (табл. 2).

Таблица 2

	Свободный член	x1	x2	x3
E	0	2	2	– 1
y1	10	– 1	– 1	1
y2	– 5	– 2	1	5
y3	10	1	– 1	0
y4	6	2	1	4

Этап 2. Проверить наличие ОДР, т.е. совместимость ограничений. На основе симплекс-таблицы (табл. 2) несовместимость проверяется по следующему признаку.

Признак 1. Ограничения будут совместны, если на каждой итерации в каждой строке, где располагается отрицательный свободный член, имеется хотя бы один отрицательный элемент. Из табл. 2 видно, что признак удовлетворяется. Так как такая проверка произведена только на одной итерации (у₂), сделать вывод о полной совместимости ограничений невозможно.

Этап 3. Найти допустимое решение.

Признак 2. Решение будет допустимым, если в симплекс-таблице все свободные члены (кроме строки целевой функции, которая не рассматривается) неотрицательные.

Значит, при поиске допустимого решения задача сводится к тому, чтобы найти множество таких свободных переменных, при котором базисные переменные (у₁, у₂, у₃, у₄), равные свободным членам, были бы неотрицательными. Если это требование не выполняется, необходимо обменять переменные. На каждой итерации такого обмена одна переменная из свободных членов переводится в базисные, а одна базисная – в свободные члены.

Шаг 1. Выбрать разрешающий элемент. В строке, содержащей отрицательный свободный член, выбрать отрицательный элемент. Столбец, в котором находится выбранный элемент, принять в качестве разрешающего.

Для примера (табл. 2) в качестве разрешающего столбца может быть принят столбец х₁. Выбор столбца в случае неоднозначности может оказать влияние на нахождение вершины ОДР, соответствующей допустимому решению. При этом различные столбцы могут привести к различным допустимым решениям и к различному числу итераций, в результате которых находится допустимое решение. Однако на оптимальное решение выбор столбца не зависит.

В рассматриваемом примере в качестве разрешающего столбца принимаем столбец х₁ (табл. 2, столбец выделен).

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

Для нашего случая (табл. 2) min = min{2,5;10;3}=2,5.

В качестве разрешающей строки принимается строка у₂ (табл. 2, строка выделена). В качестве разрешающего элемента выбираем элемент, принадлежащий разрешающему столбцу и разрешающей строке a_ij (элемент a_ij = а₂₁= –2, смотри табл. 1 и 2).

Шаг 2. Заполнить ячейки новой симплекс таблицы (табл. 3) по следующим правилам: ячейку разрешающего элемента заполнить  = 1/a_ij = – 0,5, где a_ij – разрешающий элемент; ячейки разрешающей строки заполнить элементами, стоящими в этих ячейках табл. 2, умноженными на ; ячейки разрешающего столбца – элементами, стоящими в этих ячейках табл. 2 на –  (минус лямбда); все остальные ячейки заполнить произведением чисел в разрешающей строке табл. 2 с числами в разрешающем столбце табл. 3, находящимися в той же строке и в том же столбце, в которых расположена данная ячейка.

Шаг 3. Перейти к следующей симплекс-таблице (табл. 4).

В симплекс-таблице (табл. 4) поменять местами обмениваемые переменные у₃ и х₁; в разрешающих строке и столбце записать числа, стоящие в данных ячейках табл. 3; в остальных ячейках записать сумму двух величин, стоящих в этих ячейках табл. 2 и табл. 3.

Таблица 3 Таблица 4

	Свободный член	x1	x2	x3		Свободный член	у2	х2	x3
E	– 5	1	1	5	E	– 5	1	3	4
y1	2,5	–0,5	–0,5	–2,5	y1	12,5	–0,5	–1,5	–1,5
y2	2,5	–0,5	–0,5	–2,5	х1	2,5	–0,5	–0,5	–2,5
y3	–2,5	0,5	0,5	2,5	у3	7,5	0,5	–0,5	2,5
y4	–5	1	1	5	у4	1	1	2	9

Шаг 4. Проверить признаки. Если признак 2 удовлетворяется, полученное решение является допустимым. Если признак 2 не удовлетворяется, на данной итерации допустимое решение не получено. В этом случае необходимо проверить признак 1. Если он удовлетворяется, обмен переменными повторить еще раз. Если признак не удовлетворяется, допустимое решение получено быть не может.

В нашем случае (табл. 4) признак 2 удовлетворяется.

Вывод. Значения табл.4 являются допустимым решением примера, отсюда следует, что х₁ =2,5; х₂ =0; х₃ =0; у₁ =12,5; у₂ = 0; у₃ = 7,5; у₄ = 1; Е = – 5.

Этап 4. Проверить наличие оптимального решения. На основе симплекс таблицы наличие оптимального решения проверяется по двум признакам.

Признак 3а. Целевая функция будет иметь минимальное значение, если в каждом столбце, в строке целевой функции которого находится положительный элемент, располагается хотя бы один положительный элемент.

Признак 3б. Целевая функция будет иметь максимальное значение, если в каждом столбце, в строке целевой функции которого находится отрицательный элемент, располагается хотя бы один положительный элемент.

Анализируя симплекс-таблицу (табл. 4) по признакам 3а и 3б, можно заключить, что целевая функция может иметь как минимальное, так и максимальное значение.

Признак максимального значения – в строке целевой функции нет отрицательных элементов.

Признак минимального значения – в строке целевой функции столбцов у₂, х₂ и х₃ элементы данных ячеек соответственно равняются 1, 3 и 4 (положительные элементы) и в этих же столбцах располагаются положительные элементы соответственно 0,5 и 1; 2; 2,5 и 9.

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

Признак 4а. Целевая функция будет иметь максимальное значение в том случае, когда в строке целевой функции все элементы, кроме свободного члена, который не рассматривается, положительные.

Признак 4б. Целевая функция будет иметь минимальное значение в том случае, когда в строке целевой функции все элементы, кроме свободного члена, который не рассматривается, отрицательные.

Признак 4в. Если в строке целевой функции все элементы, кроме свободного члена, который не рассматривается, одного знака и при этом имеется хотя бы один нулевой элемент, то полученное оптимальное решение является альтернативным. Это значит, что существует и другой набор значений переменных, при которых целевая функция будет иметь такое же оптимальное значение.

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

В примере требуется найти максимальное и минимальное значения целевой функции. Следовательно, должны удовлетворяться признаки 4а и 4б.