Решение оптимизационных задач

Автор: Пользователь скрыл имя, 15 Февраля 2013 в 13:13, курсовая работа

Краткое описание

Первые задачи геометрического содержания, связанные с отысканием наименьших и наибольших величин, появились ещё в древние времена. Развитие промышленности в 17-18 веках привело к необходимости исследования более сложных задач на экстремум и к появлению вариационного исчисления. Однако лишь в 20 веке при огромном размахе производства и осознанию ограниченности ресурсов Земли во весь рост встала задача оптимального использования энергии, материалов, рабочего времени, большую актуальность приобрели вопросы наилучшего в том или ином смысле управления различными процессами физики, техники, экономики и др.

ВВЕДЕНИЕ 6
1 ИСТОРИЧЕСКАЯ СПРАВКА 7
2 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕОРИИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 8
3 СИМПЛЕКС МЕТОД 9
3.1 Теоретическая часть 9
3.2 Практическая часть 14
4 ТРАНСПОРТНАЯ ЗАДАЧА 19
4.1 Теоретическая часть 19
4.2 Практическая часть 20
ЗАКЛЮЧЕНИЕ 22
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 23

Скачать в ZIP (666.79 Кб) Сколько стоит заказать работу?

Файлы: 1 файл

ММ.doc

— 1.15 Мб (Скачать)

В таблице 2 первые m строк определяются исходными планами задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора Р₀ записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора Р_j-значение ∆_j = z_j – c_j.

Значение z_j находится как скалярное произведение вектора Р_j на вектор .

(9)

Значение F₀ равно скалярному произведению вектора Р₀ на вектор С_б:

(10)

Таблица 2–Итерация 1

Базис

С_б

…

m+1

…

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

В первом случае на основании признака оптимальности исходный опорный план является оптимальным. Во втором случае целевая функция неограниченна сверху на множестве планов, а в третьем случае можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится. Этот переход от одного опорного плана к другому осуществляется исключительно из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вектора, вводимого в базис, можно взять любой из векторов Р, имеющих индекс j, для которого ∆_j <0 . Пусть, например, ∆_k<0 и решено ввести в базис вектор Р_k.

Для определения вектора, подлежащего исключению из базиса, находят для всех а_ik > 0. Пусть этот минимум достигается при i = r. Тогда из базиса исключают вектор Р_r , а число а_rk называют разрешающим элементом.

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

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

(11)

а коэффициенты разложения векторов Рi через векторы нового базиса,

(12)

После вычисления и согласно формулам (11) и (12) их значения заносят в следующую симплекс-таблицу. Элементы (m+1)-й строки этой таблицы могут быть вычислены либо по формулам:

, (13)

либо на основании их определения.

Наличие двух способов нахождения элементов (m+1)-й строки позволяет осуществлять контроль правильности проводимых вычислений.

Из формулы (13) следует, что при переходе от одного опорного плана к другому наиболее целесообразно ввести в базис вектор Р_j , имеющий индекс j, при котором максимальным по абсолютной величине является число (∆_j<0, а_j>0). Однако с целью упрощения вычислительного процесса в дальнейшем будет вектор, вводимый в базис, определять, исходя из максимальной абсолютной величины отрицательных чисел ∆_j. Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же индекс, как максимальное из чисел С_j , определяемых данными числами ∆_j (∆_j <0).

Итак, переход от одного опорного плана к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы можно вычислить как с помощью рекуррентных формул (11)–(12) так и правилам, непосредственно вытекающих из них. Эти правила состоят в следующем.

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

Элементы векторов Р₀ и Р_j в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце С_б в строке вводимого вектора проставляют величину С_k , где к- индекс вводимого вектора.

Остальные элементы столбцов вектора Р₀ и Р_j новой симплекс-таблицы вычисляют по правилу треугольника. Для вычисления, какого-нибудь из этих элементов находят три числа:

число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;

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

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

После заполнения новой симплекс-таблицы просматривают элементы (m+1)–й строки. Если все z`_j – с_j ≥ 0, то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя вышеописанную последовательность действий, находят новый опорный план. Этот процесс продолжается до тех пор, пока либо не получают оптимальный план задачи, либо не устанавливают ее неразрешимость.

Этапы решения задач симплексным методом:

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

– по формулам (11)–(12) определяют, положительные компоненты нового опорного плана, коэффициенты разложения векторов Р_j по векторам нового базиса и числа , . Все эти числа записываются в новой симплекс-таблице;

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

3.2 Практическая часть

Задача 1: Решить задачу симплекс-методом:

при условиях

где , , .

Решение:

Запишем задачу в каноническом виде:

при условиях

где , , , , , .

Запишем задачу в векторной форме:

P₁x₁+ P₂x₂+ P₃x₃+ P₄x₄+ P₅x₅+ P₆x₆ =P₀

где , , , , , , .

P₄, P₅ , P₆ – единичные базисные вектора.

Таблица 3 – Итерация 1

i	Базис	С_б	Р_о	3	2	-5	0	0	0
i	Базис	С_б	Р_о	P₁	Р₂	Р₃	Р₄	P₅	Р₆
1	Р₄	0	30	2	-3	5	1	0	0
2	Р₅	0	24	-3	-3	6	0	1	0
3	Р₆	0	28	4	2	-4	0	0	1
			0	-3	-2	5	0	0	0

Опорный план X₁=(0;0;0;30;24;28) не является оптимальным т.к. <0, <0 mах( |-3| , |-2| )=3 направляющий столбец P₁.

направляющая строка третья

Разрешающий элемент равен 4. Исключим из базиса вектор Р₆ и введем в базис вектор P₁. Составим новую симплекс-таблицу.

Таблица 4 – Итерация 2

i	Базис	С_б	Р_о	3	2	-5	0	0	0
i	Базис	С_б	Р_о	P₁	Р₂	Р₃	Р₄	P₅	Р₆
1	Р₄	0	16	0	-4	7	1	0	0
2	Р₅	0	45	0	-3/2	3	0	1	0
3	Р₁	3	7	1		-1	0	0
			21	0		2	0	0

Опорный план X₂=(7; 0; 0;16; 45; 0) не является оптимальным т.к. <0.

Направляющий столбец P₂.

, направляющая строка третья

Разрешающий элемент равен . Исключим из базиса вектор Р₁ и введем в базис вектор P₂. Составим новую симплекс-таблицу.

Таблица 5 – Итерация 3

i	Базис	С_б	Р_о	3	2	-5	0	0	0
i	Базис	С_б	Р_о	P₁	Р₂	Р₃	Р₄	P₅	Р₆
1	Р₄	0	72	8	0	-1	1	0
2	Р₅	0	66	3	0	0	0	1
3	Р₂	2	14	2	1	-2	0	0
			28	1	0	1	0	0	1

Информация о работе Решение оптимизационных задач

Решение оптимизационных задач

Краткое описание

Оглавление

Файлы: 1 файл

ММ.doc

3.2 Практическая часть