3. Решение детерминированной задачи.

Для решения ЗЛП с помощью программы необходимо привести систему ограничений к стандартной форме с выделенной единичной матрицей коэффициентов системы ограничений /2/. Все переменные модели разделятся на исходные, дополнительные и искусственные.

Рассмотрим порядок решения задачи линейного программирования с помощью программы на следующем примере:

max z = -x₁ + 2x₂ + x₃

2x₁ + 3x₂ - 5x₃  3

-x₁ + 9x₂ - x₃  5

4x₁ + 6x₂ + 3x₃  15

x_i  0

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

max z = -x₁ + 2x₂ + x₃

2x₁ + 3x₂ - 5x₃ - x₄ = 3

-x₁ + 9x₂ - x₃ - x₅ = 5

4x₁ + 6x₂ + 3x₃ + x₆ = 15

x_i  0

Матрица системы ограничений не содержит выделенной единичной матрицы:

.

Для запуска вычислительных процедур симплекс-метода необходимо ввести в модель искусственные переменные таким образом, чтобы в матрице А была явно выделена единичная матрица. Для этого необходимо в матрицу А ввести единичные вектор-столбцы, связанные со 2-ой и 3-ей строкой:

.

Теперь матрица А содержит единичную матрицу, связанную с тремя последними столбцами, причем столбцы 7 и 8 ассоциируются с введенными искусственными переменными. Для удобства дальнейших вычислений целесообразно представить единичную матрицу в диагональном виде перестановкой столбцов матрицы А, что эквивалентно перенумерации переменных модели:

.

В данной матрице столбцы 6 и 7 связаны с искусственными переменными.

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

max z = -x₁ + 2x₂ + x₃ - Mx₆ - Mx₇

2x₁ + 3x₂ - 5x₃ - x₄ + x₆ = 3

-x₁ + 9x₂ - x₃ - x₅ + x₇ = 5

4x₁ + 6x₂ + 3x₃ + x₈ = 15

x_i  0

Модель содержит 8 переменных, из них x₁, х₂, х₃ - исходные, х₄, х₅, х₈ - дополнительные, х₆ и х₇ - искусственные. Искусственные переменные вводятся в целевую функцию со штрафом М (в задаче максимизации искусственные переменные входят в целевую функцию со штрафом -М).

Исходные данные модели имеют вид:

= (-1; 2; 1; 0; 0; -М; -М; 0) - вектор коэффициентов целевой функции;

- матрица коэффициентов системы ограничений;

- вектор правых частей системы ограничений.

Вектор целевой функции раскладывается на два слагаемых:

,

где содержит коэффициенты при исходных переменных, а - при искусственных. Для рассматриваемой модели: = (-1; 2; 1; 0; 0; 0 ; 0; 0), = (0; 0; 0; 0; 0; -1; -1; 0).

Примечание. Если решается задача минимизации, то ненулевые компоненты вектора равны 1.

Для запуска программы надо загрузить в табличный процессор Excel файл zlp-mp.xls и активировать лист Расчет, на котором находятся 5 управляющих кнопок и, возможно, результаты предыдущего расчета.

Для начала работы с программой необходимо заполнить исходную таблицу на листе Расчет. В исходную таблицу вводятся следующие значения:

1) число переменных задачи n, то есть размерность вектора ;

2) число ограничений m, то есть количество строк в матрице А;

3) признак оптимизации, равный 1, если решается задача максимизации и 0, если решается задача минимизации;

4. число этапов моделирования (при решении ЗЛП с детерминированными исходными данными число этапов принимается равным 1).

В рассматриваемом случае исходная таблица имеет вид:

Таблица 1.

1	Число переменных	8
2	Число ограничений	3
3	Признак оптимизации	1
4	Число этапов моделирования	1

После заполнения исходной таблицы нужно нажать кнопку "Формирование таблиц". На лист Расчет будут выведены следующие таблицы для ввода детерминированных исходных данных ЗЛП:

1) "Коэффициенты целевой функции" - массив для ввода коэффициентов целевой функции при исходных переменных задачи (вектор );

2) "Фиктивные слагаемые коэффициентов целевой функции" - массив для ввода признаков искусственных переменных (вектор );

3) "Номера базисных переменных" - массив с номерами переменных x_j , которые используются в качестве переменных начального базиса. Если в задаче были введены искусственные переменные, то целесообразно их использование для формирования начального базиса.

4) "Матрица коэффициентов" - таблица для ввода матрицы удельных расходов ресурсов А и вектора запасов ресурсов .

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

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

Для правильной отработки программы при нажатии клавиши "Решение ЗЛП" необходимо, чтобы выполнялись следующие ограничения: 2 £ n £ 50 , 2 £ m £ 50, признак оптимизации равен 1 (соответствует задаче максимизации) или 0 (соответствует задаче минимизации).

Следует помнить, что после заполнения таблицы исходных данных ЗЛП нельзя менять значения n (число переменных) и m (число ограничений) в исходной таблице на листе Расчет перед нажатием кнопки "Решение ЗЛП".

После отработки модуля программы, реализующего алгоритм симплекс-метода, на лист Расчет выводится результирующая симплекс-таблица с одним из следующих сообщений:

1. "Условие оптимальности выполняется";

2) "Неограниченная ОДР".

В первом случае результирующая симплекс-таблица соответствует оптимальному решению ЗЛП с искусственными переменными, которое совпадает с оптимальным решением исходной задачи, если все искусственные переменные равны 0. Искусственные переменные равны 0, если они не входят в состав базисных переменных или их значения равны 0 в столбце "правые части" результирующей таблицы. Если искусственные переменные отсутствуют в оптимальном базисе, то данные таблицы могут быть использованы для дальнейшего анализа. Если искусственные переменные присутствуют в оптимальном базисе, то исходная задача не имеет допустимых решений. Во втором случае результирующая симплекс-таблица соответствует итерации симплекс-метода, на которой была обнаружена невозможность получения оптимального решения из-за неограниченности ОДР.

Для рассматриваемого примера после нажатия кнопки "Формирование таблиц" на лист Расчет выводятся таблицы, в которые заносятся исходные данные модели в следующем виде.

Таблица 2.

Коэффициенты целевой функции

	х1	х2	х3	х4	х5	х6	х7	х8
c	-1	2	1	0	0	0	0	0

Таблица 3.

Фиктивные слагаемые коэффициентов целевой функции

	х1	х2	х3	х4	х5	х6	х7	х8
cm	0	0	0	0	0	-1	-1	0

Таблица 4.

Номера базисных переменных

	огр.1	огр.2	огр.3
x	6	7	8

Таблица 5.

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	x7	x8	правые части
огр. 1	2	3	-5	-1	0	1	0	0	3
огр. 2	-1	9	-1	0	-1	0	1	0	5
огр. 3	4	6	3	0	0	0	0	1	15

После нажатия кнопки "Решение ЗЛП" на лист Расчет выводится результирующая симплекс-таблица с сообщением об оптимальности соответствующего решения. Лист Расчет имеет вид.

Таблица 6.

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	x8	правые части
z	2.333	0	0	0	0	0	0	0.333	5.000
zm	0	0	0	0	0	1	1	0	0.000
x5	7	0	0	-0.846	1	0.846	-1	1.077	13.692
x2	0.667	1	0	-0.077	0	0.077	0	0.128	2.154
x3	0	0	1	0.154	0	-0.154	0	0.077	0.692

Условие оптимальности выполняется

После строки заголовков таблицы следует две строки оценок плана /2/. Для того, чтобы получить значение оценки плана k_j , связанной с переменной x_j , используется формула:

k_j = z_j + Mz_mj ,

где z_j - коэффициент строки ²z² симплекс-таблицы при переменной x_j ,

z_mj - коэффициент строки ²zm² симплекс-таблицы при переменной x_j .

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

Состав переменных оптимального базиса указан в первом столбце, начиная с 4-ой строки. Значения оптимальных базисных переменных указаны в соответствующих строках столбца "правые части". Небазисные переменные равны 0.

При решении ЗЛП интерес представляют оптимальные значения исходных переменных задачи, то есть в данном случае x₁, х₂, х₃, а также оптимальное значение целевой функции z. Из полученной таблицы эти значения равны:

x₁ = 0, x₂ = 2.154, x₃ = 0.692, z = 5.0.