Решение задач симплекс-методом

Размещено на http://allbest.ru

Введение

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

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

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

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

1. находится план;

2. проверяют план на оптимальность;

3. если псевдоплан оптимален, решение заканчивается, иначе устанавливается неразрешение задачи, либо переходят который новому псевдоплану;

4. выбирают разрешающую строку и разрешающий столбец;

5. находят новый псевдоплан и переходят который пункту 2

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

симплекс программирование интерфейс delphi



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

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

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

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

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

1) Дать формализованное описание задачи

2) Сформулировать двойственную задачу к исходной

3) Указанную задачу решить двойственным симплекс-методом

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

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

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

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ > max

a_1,1x₁+a_1,2x₂+...a_1,nx_n + x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n +x_n+2 =b₂

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m

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

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

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

F=a_0,1x₁+a_0,2x₂+...a_0,nx_n +b₀ > max

a_1,1x₁+a_1,2x₂+...a_1,nx_n+x_n+1=b₁

a_2,1x₁+a_2,2x₂+...a_2,nx_n+x_n+2=b₂

a_m,1x₁+a_m,2x₂+...a_m,nx_n+x_n+m=b_m



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

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

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

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

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

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

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

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

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

a_0,l=min{a_0,i }

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

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

Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке 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) этой системы уравнений имеет вид:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

x4 = 61/2

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



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

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

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



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

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

Delphi (Демльфи, произносится /?d?lfi/) -- язык программирования, который используется в одноимённой среде разработки. Название используется начиная с 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 Тестирование программного средства с помощью указанной задачи

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

Рис. 5

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

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

Рис. 6

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

Рис. 7

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



Рис. 8

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

Рис. 9

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

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



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

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

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

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

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

устройства

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

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

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

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

устройства

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

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

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

Размещено на Allbest.ru

...