Файл: zlp-mp.doc

Примечание. Если решается задача минимизации, то ненулевые компоненты вектора равны 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.

---