Файл: Е.В. Буйная Симплексный метод решения оптимизационных задач.pdf

8

Пример 2.

Пусть стоит задача минимизации

L(X) = -5X1 + 2X2

при условиях

-5X1 + X2 ≤ -10

X1 - X2 = 10

Приводим исходную задачу к каноническому виду:

1. Расписываем переменные X1 и X2 через разность двух неотрица-

тельных переменных, т.е. X1 = X1’ - X1’’ и X2 = X2’ – X2’’, где X1’, X1’’,

X2’, X2’’ ≥ 0.

2. Первое ограничение умножаем на (-1) и вводим ослабляющую переменную X3 ≥ 0.

В результате переходим к задаче минимизации

L(X) = -5X1’ + 5 X1’’+ 2X2’ - 2X2’’

при условиях

5X1’ - 5X1’’ - X2’ - X2’’- X3 = 10

X1’, X1’’, X2’, X2’’, X3 ≥ 0.

3. Выбор начального опорного плана

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

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

тоду искусственного базиса.

Метод искусственного базиса заключается в том, что для получения единичной подматрицы коэффициентов мы вводим в исходную задачу неотрицательные т. н. искусственные переменные и включаем их в целевую функцию (линейную форму) с коэффициентом +М для зада-

9

чи минимизации и с коэффициентом - М для задачи минимизации, где М>0 - сколь угодно большое число.

Полученная М-задача решается до получения оптимального плана.

1. Если в оптимальном плане М-задачи значения искусственных переменных равны нулю, то значения остальных компонент образуют оптимальный план исходной задачи.

2. Если в оптимальном плане М-задачи значение хотя бы одной из искусственных переменных отлично от нуля, то исходная задача не имеет ни одного плана (ее ограничения противоречивы).

4. Примеры решения линейных задач симплексным методом

Пример 1.

Предприятие планирует закупить четыре вида сырья, которое должно использоваться на производство продукции А, Б, В в следующих пропорциях:

У предприятия имеются заказы на поставку этих видов продукции в размерах до 10, 30 и 20 единиц соответственно. В договоре предусмотрены цены поставок за единицу продукции - 10, 8 и 20 условных единиц. Рыночная цена требуемого предприятию сырья равна 2, 5, 8 и 3 у.е. за единицу сырья соответственно.

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

Решение:

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

10

1 этап. Математическая постановка задачи

В начале определим, какие величины в задаче неизвестны и что нужно найти. Так как нам необходимо определить оптимальное количество закупаемого сырья, обозначим за Х1 , Х2 , Х3 и Х4 – объемы закупки сырья соответствующих видов. В этом случае количество произведенной продукции будет равняться:

-продукции А - 0,5Х1+0,1Х2+0,2Х3;

-продукции Б - 0,2Х1+0,5Х4;

-продукции В - 0,3Х2+0,2Х3+0,2Х4.

Прибыль от реализации продукции сложится из выручки от продажи произведенной продукции за вычетом затрат на покупку необходимого сырья. Тогда данная задача запишется в виде:

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

L(X)=10(0,5X1+0,1X2+0,2X3)+8(0,2Х1+0,5Х4)+ +20(0,3Х2+0,2Х3+0,2Х4)-(2X1+5X2+8X3+3X4)

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

продукции типа А, Б, В. При их построении мы исходили из предположения, что не имеет смысла производить больше продукции, чем мы можем реализовать.

Условия (4.4)-(4.7) – естественные условия неотрицательности переменных (объемы закупки сырья не могут быть отрицательны).

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

11

2 этап. Приведение задачи к каноническому виду

В соответствии с требованиями, которые были описаны выше, нам необходимо представить ограничения (4.1)-(4.3) в виде равенств. Для этого введем ослабляющие переменные со знаком (+), так как в ограничениях знак (≤ ), и для простоты последующей работы приведем подобные члены в целевой функции. Тогда задача примет вид:

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

L ( x ) = 4 ,6 X 1 + 2 X 2 − 2 X 3 + 5 X 4

Таким образом, получена задача с 7 неизвестными и 10 ограничениями, допускающая решение стандартным симплекс-методом.

3 этап. Выбор начального опорного плана

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

С = {4,6, 2, -2, 5, 0, 0, 0} – вектор коэффициентов при переменных задачи в целевой функции.

В = {10, 30, 20} - вектор значений правых частей ограничений за-

дачи.

- матрица коэффициентов при переменных в ограничениях задачи.

Как мы видим, в матрице А присутствует единичная подматрица, которая соответствует векторам А5, А6, А7, следовательно, начальный опорный план будет выглядеть так: Х0 ={0, 0, 0, 0, 10, 30, 20}.