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

Введение

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

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

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

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

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	-	-	-

 

 

4. Пересчет симплекс-таблицы.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

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

 

 

Представим расчет каждого элемента в виде таблицы:

B	X1	X2	X3	X4	X5	X6	X7
-26-(-30 • -4):-5	-1-(-2 • -4):-5	-1-(0 • -4):-5	0-(-3 • -4):-5	-4-(-5 • -4):-5	1-(0 • -4):-5	-(1 • -4):-5	0-(0 • -4):-5
-30 : -5	-2 : -5	0 : -5	-3 : -5	-5 : -5	0 : -5	1 : -5	0 : -5
-24-(-30 • -6):-5	-1-(-2 • -6):-5	-2-(0 • -6):-5	-4-(-3 • -6):-5	-6-(-5 • -6):-5	0-(0 • -6):-5	0-(1 • -6):-5	1-(0 • -6):-5
0-(-30 • -4):-5	-5-(-2 • -4):-5	-6-(0 • -4):-5	-7-(-3 • -4):-5	-4-(-5 • -4):-5	0-(0 • -4):-5	0-(1 • -4):-5	0-(0 • -4):-5

 

 

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

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

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

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

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

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	-2	3/5	-1	22/5	0	1	-4/5	0
x4	6	2/5	0	3/5	1	0	-1/5	0
x7	12	12/5	-2	-2/5	0	0	-11/5	1
F(X0)	24	-32/5	-6	-43/5	0	0	-4/5	0
θ		-	-6 : (-1) = 6	-	-	-	-4/5 : (-4/5) = 1	-

 

 

4. Пересчет симплекс-таблицы.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x6	5/2	-3/4	5/4	-3	0	-5/4	1	0
x4	13/2	1/4	1/4	0	1	-1/4	0	0
x7	15	1/2	-1/2	-4	0	-3/2	0	1
F(X1)	26	-4	-5	-7	0	-1	0	0

 

 

Представим расчет каждого элемента в виде таблицы:

В базисном столбце все элементы положительные.

Переходим к основному алгоритму симплекс-метода.

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

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

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7
x6	5/2	-3/4	5/4	-3	0	-5/4	1	0
x4	13/2	1/4	1/4	0	1	-1/4	0	0
x7	15	1/2	-1/2	-4	0	-3/2	0	1
F(X1)	26	-4	-5	-7	0	-1	0	0

 

Оптимальный план можно записать так:

x4 = 61/2

F(X) = 4•6 1/2 = 26

 

14.Анализ полученных  результатов

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

Минимальная стоимость данного вещества F(X) = 4•6 1/2 = 26.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x6	5/2	-3/4	5/4	-3	0	-5/4	1	0
x4	13/2	1/4	1/4	0	1	-1/4	0	0
x7	15	1/2	-1/2	-4	0	-3/2	0	1
F(X1)	26	-4	-5	-7	0	-1	0	0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.Специальная  часть

2.1Выбор программного  средства для решения

        Delphi (Де́льфи, произносится /ˈdɛlˌfi/) — язык программирования, который используется в одноимённой среде разработки. Название используется начиная с 7 версии среды разработки, ранее это был Object Pascal, разработанный фирмой Borland и изначально реализованный в её пакете Borland Delphi, от которого и получил в 2003 году своё нынешнее название. Object Pascal по сути является наследником языка Pascal с объектно-ориентированными расширениями.

 Borland Delphi представляет собой средство разработки приложений для Microsoft Windows. Delphi является мощным и простым в использовании инструментом для создания автономных программ, обладающих графическим интерфейсом (GUI), или 32-битных консольных приложений (программ, которые не имеют графического интерфейса).

 

Основные составные части Delphi:

1. Дизайнер Форм (Form Designer)

2. Окно Редактора Исходного Текста (Editor Window)

3. Палитра Компонент (Component Palette)

4. Инспектор Объектов (Object Inspector)

5. Справочник (On-line help)

 

 

 

 

2.2 Экранное представление  программы. Описание интерфейса  программы.

1. В главном окне программы имеется следующие кнопки: “Выход”, “Об авторе”,  “Справка”,  “Перейти к решению” (см рис.1)

 

 
Рис(1)

2. Окно – решение. (см рис2)

Рис(2)

3. Окно – Об авторе. (см рис3)

Рис(3)

4. Окно – справка (см рис 4)

Рис(4)

 

 

 

 

 

 

2.3 Тестирование  программного средства с помощью  указанной задачи

 

Для того чтобы начать решения, необходимо запустить программу (см рис.1)

Рис.1

Далее запустится сама программа.  Для того чтобы начать решение вам необходимо  нажать кнопку “Перейти к решению”. Далее открывается другое окно в котором и производится решение данной задачи online.

Необходимо нажать на кнопку ссылка на решение, после чего ссылка появится в адресной строке программы. Далее нажимаем “Поиск”. (см рис.2)

Рис.2

 

После нажатия на кнопку поиск появится решение задачи online. Вводим наше количество переменных. (см рис.3)

Рис.3

Нажимаем – Далее. Нас просят ввести коэффициенты ограничений, выбрать нужный знак (=, >=, <=) и ввести коэффициенты в саму функцию F(x). (см рис.4)

Рис.4

Нажимаем – Далее. После чего нажимаем кнопку - посмотреть решение. (см рис.5)

 

Рис.5

Далее будет представлен расчет данной задачи в подробности. Так же можно вывести результаты в ExeL (ДОПИСАТЬ)

Так же если вы не разобрались в программе , вы можете воспользоваться справкой. Для того чтобы это сделать, на главном окне нужно нажать кнопку “Справка”.  (cм рис.6,7)

Рис.6

Рис.7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Технические  и системные требования

 

Программа «Двойственный симплекс метод.

Минимальная конфигурация:

• Тип процессора                                                Pentium 3 и выше

• Объем оперативного запоминающего           128 МВ

     устройства    

• Объем свободного места на диске                 100 МВ

Рекомендуемая конфигурация:

• Тип процессора                                                 Pentium 4

• Объем оперативного запоминающего            256 МВ

устройства

• Объем свободного места на диске                   500 МВ

Требования к программной совместимости.

Программа должна работать под управление семейства оперативных систем Win 32 (Windows Vista, XP/7/8  и т.п.).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение.