Файл: zlp-mp.doc

4. Решение злп с помощью соотношений двойственности

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

Для определения обратной матрицы базиса следует прежде всего знать порядок базисных переменных (связанных с уравнениями системы ограничений ЗЛП). Тогда матрица базиса В будет формироваться из столбцов матрицы ограничений А, связанных с текущими базисными переменными. После формирования матрицы базиса В обратная матрица определяется с помощью встроенной функции МОБР табличного процессора Excel. Определение всех остальных компонент текущей симплекс-таблицы сводится либо к произведению матриц, либо к произведению вектора на матрицу, либо к скалярному произведению векторов. Так как вектор можно интерпретировать, как матрицу, состоящую из одной строки или одного столбца, то все эти операции можно осуществить с использованием встроенной функции МУМНОЖ табличного процессора Excel.

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

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₃ - Mx₆ - Mx₇

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

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

---

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

x_i  0

Начальными базисными переменными данной модели являются x₆, x₇ , x₈ (то есть те переменные, которые связаны с вектор-столбцами единичной матрицы).

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

,

где вектор содержит числовые коэффициенты при переменных в уравнении целевой функции, а вектор - коэффициенты при символах штрафа М.

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

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

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

При этом компоненты вектора вычисляются по формуле:

Таким образом, исходные данные для решения ЗЛП с помощью встроенных функций Excel в рассматриваемом примере имеют следующий вид:

---

,

, .

Начальный базис сформирован переменными x₆ , x₇ , x₈ . Значит начальная матрица базиса В состоит из вектор-столбцов матрицы А:

.

При решении ЗЛП на ЭВМ в табличном процессоре Excel вектор коэффициентов при базисных переменных , так же как и вектор , будем представлять в виде матрицы размера , столбцы которой являются столбцами матрицы , связанными с базисными переменными:

.

Рассмотрим порядок решения ЗЛП с помощью табличного процессора Excel на примере рассматриваемой модели.

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

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

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

---

	A		B		C	D	E		F		G	H	I	J	K	L	M
1	Решение ЗЛП симплекс-методом
2	х1		х2		х3	х4	х5		х6		х7	х8
3	Вектор с
4	-1		2		1	0	0		0		0	0
5	0		0		0	0	0		-1		-1	0
6	Матрица А													Вектор b
7	2		3		-5	-1	0		1		0	0		3
8	-1		9		-1	0	-1		0		1	0		5
9	4		6		3	0	0		0		0	1		15
10	Матрица базиса В						Обратная матрица В-1
11
12
13
14	Коэффициенты базисных переменных cb
15
16
17	Двойственные переменные Y=cb*B-1
18
19
20	Вспомогательный массив F=Y*A
21
22
23	Симплекс-таблица
24	Оценки плана k=F-c
25	Матрица системы ограничений S=B-1*A
26	Значения базисных переменных xb=B-1*b
27	Значение целевой функции z=cb*xb
28			x1		x2	x3	x4		x5		x6	x7	x8		Решение		Симплекс
29	k																***
30	km																***
31
32
33
34	Включаемая переменная
35	Исключаемая переменная

---

Рис. 1. Начальный вид листа Симплекс-метод.

Для получения обратной матрицы базиса в таблице "Обратная матрица B^-1" воспользуемся встроенной функцией Excel МОБР. Для рассматриваемого примера необходимо выполнить следующие действия. Активируем ячейку Е11 и с помощью мастера функций запишем в нее функцию МОБР(массив). В качестве адреса параметра “массив” укажем адрес матрицы базиса А11-С13. Для получения элементов обратной матрицы выделим отведенную под их размещение область листа E11-G13, переместим курсор в строку формул и нажмем комбинацию клавиш Ctrl+Shift+Enter. В выделенной области E11-G13 разместится обратная матрица базиса.

При решении ЗЛП на ЭВМ вектор двойственных переменных имеет размерность . Для вычисления компонент вектора в таблице "Двойственные переменные Y=c_b*B^-1" воспользуемся функцией МУМНОЖ табличного процессора Excel. Для рассматриваемого примера необходимо выполнить следующие действия. Активируем ячейку А18 и с помощью мастера функций запишем в нее функцию МУМНОЖ(массив1, массив2). В качестве параметра массив1 выделяем матрицу компонент вектора (ячейки А15-С16), а в качестве параметра массив2 выделяем обратную матрицу базиса (ячейки Е11-G13). Для получения компонент вектора выделим отведенную под их размещение область листа А18-С19, переместим курсор в строку формул и нажмем комбинацию клавиш Ctrl+Shift+Enter. В выделенной области А18-С19 разместятся компоненты вектора . Все остальные операции перемножения матриц или векторов с помощью функции МУМНОЖ производятся аналогично и далее указываются только области расчетного листа табличного процессора Excel, соответствующие параметрам массив1, массив2 и результату их перемножения.

Для вычисления оценок плана определяется вспомогательный массив , компоненты которого заносятся в таблицу "Вспомогательный массив F=Y*A". В рассматриваемом примере для вычисления матрицы F используется функция МУМНОЖ. В качестве параметра массив1 используется область расчетного листа А18-С19, в качестве параметра массив2 - область А7-Н9, а результат выводится в область А21-Н22.

---