Файл: zlp-mp.doc

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

Для переменных текущего базиса в симплекс-таблице зарезервирована область А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-ой итерации.

---

5. Задание для лабораторной работы

1. Варианты заданий к лабораторным работам соответствуют вариантам контрольной работы “Линейное программирование” и приведены в /3/. В данной лабораторной работе следует с помощью программы “Решение и моделирование задач линейного программирования” получить решение заданий пункта 1а контрольной работы “Линейное программирование”. Таким образом, в лабораторной работе, используя программу, необходимо решить следующие задачи:

а) Решить исходную ЗЛП.

б) Решить ЗЛП с измененной целевой функцией.

в) Решить ЗЛП с измененной правой частью системы ограничений.

г) Решить ЗЛП при введении дополнительного ограничения.

д) Решить ЗЛП при введении новой переменной.

е) Для данной ЗЛП сформулировать двойственную задачу. Решить ее симплекс-методом. С помощью соотношений двойственности проверить ответ.

2. Решить исходную ЗЛП с использованием встроенных функций табличного процессора Excel.

3. Отчет лабораторной работы должен содержать:

а) Исходные данные и оптимальную симплекс-таблицу для заданий 1а-1е данного пункта, для задания 1е необходимо представить модель двойственной задачи, ее приведение к стандартной форме, исходные данные для решения на ЭВМ, оптимальную симплекс-таблицу и результаты проверки ее решения с помощью соотношений двойственности.

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

Отчет по лабораторной работе может быть выполнен на ПЭВМ и представлен в распечатанном виде. Типовой отчет приведен в приложении.

6. Литература

1.	Трушков А. С. Решение и моделирование задач линейного программирования. Отчёт и программная документация. - КФ МГОУ, г. Коломна, 1998 г., 76 с.
2.	Трушков А. С. Симплексный метод решения задач линейного программирования. Алгоритмы и приложения.// Учебное пособие. Изд-во КФ МГОУ, г. Коломна, 1996 г., 107 с.
3.	Трушков А.С. Контрольная работа “Линейное программирование”.// Сборник вариантов контрольной работы. Изд-во КФ МГОУ, г. Коломна, 1996 г., 66 с.

---