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.

Все исходные данные для определения компонент текущей симплекс-таблицы определены и выведены на расчетный лист. Разметка симплекс-таблицы и необходимые формулы выведены программой на лист Симплекс-метод. Рассмотрим процедуру программирования симплекс-таблицы для рассматриваемого примера.

Для переменных текущего базиса в симплекс-таблице зарезервирована область А31-А33. Для рассматриваемого примера начальный базис сформирован переменными х₆, х₇, х₈ и их обозначения вносятся в эту область.

В область расчетного листа B29-I30 заносятся значения оценок плана в соответствии с формулой:

.

Для этого из ячеек области А21-Н22 вычитаются соответствующие значения из области А4-Н5. Для организации этой операции следует выполнить следующие действия:

1) выделить ячейку В29;

2) активировать курсор в строке формул, в которую ввести следующую строку: “=А21-А4”, нажать клавишу Enter;

3) выделить ячейку В29, “зацепить” манипулятором “мышь” правый нижний угол выделенной ячейки и “растянуть” выделенную область на диапазон ячеек В29-I30.

Определение матрицы S левой части симплекс-таблицы производится с помощью соотношения двойственности:

.

Для вычисления компонент матрицы S используется функция МУМНОЖ. В качестве параметра массив1 используется область расчетного листа Е11-G13, в качестве параметра массив2 - область А7-Н9, а результат выводится в область B31-I33.

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

.

Для вычисления компонент вектора используется функция МУМНОЖ. В качестве параметра массив1 используется область расчетного листа Е11-G13, в качестве параметра массив2 - область J7-J9, а результат выводится в область K31-K33.

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

Для вычисления компонент целевой функции z используется функция табличного процессора Excel МУМНОЖ. В качестве параметра массив1 используется область расчетного листа А15-С16, в качестве параметра массив2 - область K31-K33, а результат выводится в область K29-K30.

Таким образом, определены все компоненты текущей симплекс-таблицы, связанные с выбранным набором базисных переменных, а значит и с однозначно определенными матрицей базиса В и вектором (а фактически, матрицей) коэффициентов целевой функции при базисных переменных. В дальнейших преобразованиях должны согласовано изменяться набор базисных переменных в столбце А31-А33, матрица базиса в области А11-С13 и коэффициенты базисных переменных в области А15-С16.

В соответствии с алгоритмом решения ЗЛП для задачи максимизации выберем максимальную отрицательную оценку плану. Сначала необходимо сравнить между собой компоненты вектора , являющиеся числовыми коэффициентами перед символом штрафа М и записанные в строке с заголовком “km”. Если все эти компоненты неотрицательны (в задаче максимизации), то необходимо производить сравнение для компонент вектора , записанных в строке с заголовком “k” (соответствующих только нулевым компонентам в строке “km”). В рассматриваемом примере максимальная неотрицательная компонента в строке с заголовком “km” соответствует переменной x₂. Значит столбец с заголовком “х₂” выбирается в качестве ведущего столбца и переменная x₂ на следующей итерации включается в число базисных переменных. Этот факт отметим, указывая номер 2 в ячейке Е34 расчетного листа.

Для определения исключаемой из базиса переменной вычислим симплекс-множители данной таблицы. Для этого разделим значения текущих базисных переменных (т.е. элементы области К31-К33) на соответствующие элементы выбранного ведущего столбца (расположенные в области С31-С33). Результат деления запишем в область М31-М33. Выполняемые при этом действия аналогичны операциям, выполняемым при вычислении оценок плана .

В соответствии с теорией симплекс-метода, среди неотрицательных значений симплекс-множителей выбирается минимальное и определяется соответствующая ему базисная переменная. В рассматриваемом примере это переменная х₇, которая принимается в качестве исключаемой из базиса переменной. В ячейку Е35 вводим номер 7 исключаемой из базиса переменной.

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

Таким образом, на следующей итерации переменная х₂ вводится в базис вместо переменной х₇. Для выполнения следующей итерации необходимо сделать следующие действия (в рассматриваемом примере):

1) очистить ячейки Е34 и Е35 от номеров включаемой и исключаемой из базиса переменных;

2) в списке базисных переменных в ячейке А32 изменить базисную переменную: вместо "х7" записать "х2";

3) область М31-М33 очистить от значений симплекс-множителей;

4) так как изменилась вторая компонента в списке базисных переменных (вместо х₇ в базис вошла в качестве второй компоненты х₂) в матрице базиса В необходимо заменить второй столбец В11-В13: вместо вектора включается вектор матрицы А. Аналогично, в векторе коэффициентов целевой функции при базисных переменных вторая компонента (В15-В16) изменяется: вместо 7-го столбца таблицы "Вектор с" вносится 2-ой столбец этой таблицы.

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

	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	1		0		0		1		0		0
12	0		1		0		0		1		0
13	0		0		1		0		0		1
14	Коэффициенты базисных переменных cb
15	0		0		0
16	-1		-1		0
17	Двойственные переменные Y=cb*B^-1
18	0		0		0
19	-1		-1		0
20	Вспомогательный массив F=Y*A
21	0	0		0		0	0	0		0		0
22	-1	-12		6		1	1	-1		-1		0
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		1		-2	-1	0		0		0	0	0		0		***
30	km		-1		-12	6	1		1		0	0	0		-8		***
31	х6		2		3	-5	-1		0		1	0	0		3		1
32	х7		-1		9	-1	0		-1		0	1	0		5		0.556
33	х8		4		6	3	0		0		0	0	1		15		2.5
34	Включаемая переменная						2
35	Исключаемая переменная						7

Рис. 2. Вид листа Симплекс-метод после 1-ой итерации.