Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Южно-Уральский государственный университет»

(Научно-исследовательский университет)

Горно-керамический колледж

филиала ЮУрГУ в г. Сатке

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОМУ ПРОЕКТУ

по дисциплине: «Математические методы»

ГКК - 230105.51.2012.18.ПЗ КП

Нормоконтролер, преподаватель	Руководитель, преподаватель
_______________О.И.Шибанова	_____________О.И. Шибанова
______________________2012 г.	____________________2012 г.

		Автор проекта
		студент группы 305
		______________ И.А. Савинков
		_____________________2012 г.

		Проект защищен
		с оценкой (прописью, цифрой)
		___________________
		___________________2012 г.

Сатка 2012
Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Южно-Уральский государственный университет»

(Научно-исследовательский университет)

Горно-керамический колледж

филиала ЮУрГУ в г. Сатке

Специальность 230105.51 «Программное обеспечение вычислительной

техники и автоматизированных систем»_______________

УТВЕРЖДАЮ

Председатель ПЦК

_________/Шибанова О.И.

___________ 2012 г.

ЗАДАНИЕ

на курсовой проект студента

Савинкова Ильи Александровича

Группа 305

Дисциплина (специализация) Математические методы
Тема работы (проект) Решение оптимизационных задач

Вариант - 18

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

Задача 1: Сформулировать двойственную задачу и решить её.

при условиях

где , , .

Задача 2: На базы: А₁, А₂ ... A₄ поступил однородный груз в количествах: а₁, а₂, а₃, а₄ соответственно. Груз требуется перевезти в пять пунктов: b₁ в пункт В₁, b₂ в пункт В₂, b₃ в пункт В₃, b₄ в пункт В₄, b₅ в пункт В₅.

Спланировать перевозки так, чтобы общая их стоимость была минимальной.

Матрица тарифов c_ij перевозок между пунктами отправления (базами) и пунктами назначения, а также запасы а_i и потребности b_j задаются в соответствии с таблицей.

Найти опорный план задачи методом северо-западного угла и методом минимального элемента. Оптимальный план определить с помощью MS Excel, MathCAD.

Пункт отправления	Пункты назначения					Запасы, a_i (тонн)
Пункт отправления	В₁	B₂	В₃	B₄	B₅	Запасы, a_i (тонн)
A₁	11	28	15	12	17	4
A₂	32	27	26	10	3	6
Aз	12	4	22	3	1	10
A₄	4	1	5	4	24	10
Потребности, b_j (тонн)	7	7	7	7	2

Календарный план:

Наименование разделов курсового проекта	Срок выполнения разделов проекта	Отметка о выполнении руководителя
Разработка графического метода решения задачи линейного программирования	27.12.2012г.
Разработка симплекс-метода решения задачи линейного программирования	15.03.2013г.
Решение транспортной задачи	4.04.2013г.
Оформление курсовой работы	12.05.2013г.

Руководитель работы (проекта) __________________ /О. И. Шибанова /

Студент _____________ /И.А. Савинков/

АННОТАЦИЯ

Савинков И.А. Решение оптимизационных задач. - Сатка: Горно- керамический колледж филиала ЮУрГУ, 305; 2012, 24 с., 10 ил., библиографический список - 8 наим., 1 прил.

В курсовом проекте рассмотрены решения оптимизационных задач.

Каждый раздел состоит из теоретической и практической части.

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

Первая задача решена графическим методом с помощью математического пакета MathCAD 14 Professional.

Алгоритм симплекс-метода использован при решении первой задачи. Подтверждение правильного решения осуществлено при помощи функции Поиск решения в MS Excel, программного кода в MathCAD 14 Professional.

Опорный план второй задачи – транспортной, определён методом северо-западного угла, а также методом минимального элемента. Оптимальный план перевозок получен с помощью метода потенциалов.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

Задачи оптимального планирования,

задачи линейного программирования

методами линейного программирования.

1 ИСТОРИЧЕСКАЯ СПРАВКА

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

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича «Математические методы организации и планирования производства». Поскольку методы, изложенные Л.В.Канторовичем, были малопригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти незамеченной.

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т. Купманс получили Нобелевскую премию по экономическим наукам за «вклад в разработку теории и оптимального использования ресурсов в экономике».

2 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕОРИИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

Таблица 1 – Общая задача линейного программирования

Каноническая

(основная) форма

Стандартная

(симметрическая) форма

Общая форма

1) ограничения

Уравнения

Неравенства

Уравнения,

неравенства

2) условия неотрицательности

Все переменные

Часть переменных

3) целевая функция

max или min F(x)

(max F(x))

(min F(x))

max или min F(x)

Планом или допустимым решением задачи линейного программирования называется вектор , удовлетворяющий условиям 1) и 2).

Оптимальным планом (решением) задачи линейного программирования называется план, доставляющий линейной форме наибольшее или наименьшее значение.

3 СИМПЛЕКС МЕТОД

3.1 Теоретическая часть

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

Пусть требуется найти максимальное значение функции

(4)

при условиях

. (5)

Здесь а_ij, b_i, и c_j (i=1,…, m; j=1,…, n) – заданные постоянные числа (m<n и b_i>0).

Векторная форма данной задачи имеет следующий вид: найти максимум функции

(6)

при условиях

. (7)

где ; ; …; ; …; ; .

Так как b₁P₁+ b₂P₂ +…+ b_mP_m = P₀, то по определению опорного плана Х=(b₁; b₂; …; b_m; 0; …; 0) является опорным планом данной задачи (последние n–m компонент вектора Х равны нулю). Этот план определяется системой единичных векторов Р₁, Р₂, …, Р_m, которые образуют базис m–мерного пространства. Поэтому каждый из векторов Р₁, Р₂, …, Р_m, а так же вектор Р₀ могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть

(8)

Положим ; .

Так как векторы Р₁, Р₂, …, Р_m, единичные, то и , а

Теорема 1 (признак оптимальности опорного плана):

Опорный план является оптимальным, если ∆_j > 0 для любого .

Теорема 2: Если ∆_k < 0 для некоторого j=k и среди чисел a_ik нет положительных (a_ik < 0), то целевая функция не ограничена на множестве ее планов.

Теорема 3: Если опорный план Х задачи не вырожден и ∆_k < 0, но среди чисел a_ik есть положительные (не все a_ik < 0), то существует опорный план Х′ такой, что F(X′)>F(X). Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.

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

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

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

В таблице 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