Двойственный симплекс метод

Введение

Двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами. В обычном симплексном алгоритме план всегда должен быть допустимым.

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

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

Алгоритм двойственного симлекс метода:

1. находится план; 
2. проверяют план на оптимальность; 
3. если псевдоплан оптимален, решение заканчивается, иначе устанавливается неразрешение задачи, либо переходят который новому псевдоплану; 
4. выбирают разрешающую строку и разрешающий столбец; 
5. находят новый псевдоплан и переходят который пункту 2

Цель курсовой работы: приобрести навыки решения двойственно задачи с использованием объектно-ориентированного и визуального программирования.

1.Основная часть

1.1 Математическая  постановка задачи курсового  проекта 

Двойственный симплекс метод

Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее 26ед. химического вещества А. 30ед. – вещества В и 24 ед. – вещества С. Количество единиц химического вещества, содержащегося в 1кг  сырья каждого вида, указанно в таблице. В ней же приведена цена сырья каждого вида.

Вещество	Количество единиц вещества, содержащегося в 1 кг сырья вида
	1	2	3	4
А	1	1	-	4
В	2	-	3	5
С	1	2	4	6
Цена 1 кг сырья (руб.)	5	6	7	4

 

 

Составить смесь, содержащую не менее нужного количества вещества данного вида и имеющую минимальную стоимость.

1. Дать формализованное описание задачи
2. Сформулировать двойственную задачу к исходной
3. Указанную задачу решить двойственным симплекс методом

 

 

 

 

 

 

 

 

 

1.2 Описание метода  решения

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

F=a0,1x1+a0,2x2+...a0,nxn +b0 → max

a1,1x1+a1,2x2+...a1,nxn + xn+1=b1

a2,1x1+a2,2x2+...a2,nxn +xn+2 =b2

.......................................

am,1x1+am,2x2+...am,nxn+xn+m=bm

Исходная таблица для задачи имеет следующий вид:

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

 

x1, x2, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.

 

  Алгоритм симплекс-метода.

 

  Подготовительный этап

 

 Приводим задачу ЛП  к каноническому виду

F=a0,1x1+a0,2x2+...a0,nxn +b0 → max

a1,1x1+a1,2x2+...a1,nxn+xn+1=b1

a2,1x1+a2,2x2+...a2,nxn+xn+2=b2

.......................................

am,1x1+am,2x2+...am,nxn+xn+m=bm

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.  

 

 Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

 

 

 

 

 Шаг 1. Проверка на допустимость.   

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.

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

Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то ко второму.

 

 Шаг 2. Проверка на оптимальность.

 

 На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находящихся в строке F (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0)

a0,l=min{a0,i }

l - столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.

bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0

k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

 

 

 

 

 

 

 

 

 

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

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

Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).

Определим минимальное значение целевой функции F(X) = 5x1 + 6x2 + 7x3 + 4x4 при следующих условиях- ограничений.

- x1 - x2 - 4x4≤-26

- 2x1 - 3x3 - 5x4≤-30

- x1 - 2x2 - 4x3 - 6x4≤-24

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7.

-1x1-1x2 + 0x3-4x4 + 1x5 + 0x6 + 0x7 = -26

-2x1 + 0x2-3x3-5x4 + 0x5 + 1x6 + 0x7 = -30

-1x1-2x2-4x3-6x4 + 0x5 + 0x6 + 1x7 = -24

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

 

-1	-1	0	-4	1	0	0
-2	0	-3	-5	0	1	0
-1	-2	-4	-6	0	0	1

 

 

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

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

Решим систему уравнений относительно базисных переменных: x5, x6, x7

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,-26,-30,-24)

Базисное решение называется допустимым, если оно неотрицательно.

 

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	-26	-1	-1	0	-4	1	0	0
x6	-30	-2	0	-3	-5	0	1	0
x7	-24	-1	-2	-4	-6	0	0	1
F(X0)	0	-5	-6	-7	-4	0	0	0

 

 

1. Проверка критерия оптимальности.

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

2. Определение новой свободной  переменной.

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 2-ая строка, а переменную x6 следует вывести из базиса.

3. Определение новой базисной  переменной.

Минимальное значение θ соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-5).

 

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	-26	-1	-1	0	-4	1	0	0
x6	-30	-2	0	-3	-5	0	1	0
x7	-24	-1	-2	-4	-6	0	0	1
F(X0)	0	-5	-6	-7	-4	0	0	0
θ		-5 : (-2) = 21/2	-	-7 : (-3) = 21/3	-4 : (-5) = 4/5	-	-	-