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

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

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

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

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

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

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

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

 

 

 

 

 

 

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

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

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

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

ГКК - 230105.51.2012.18.ПЗ КП

 

 

Нормоконтролер, преподаватель	Руководитель, преподаватель
_______________О.И.Шибанова	_____________О.И. Шибанова
______________________2012 г.	____________________2012 г.
		Автор проекта
		студент группы 305
		______________ И.А. Савинков
		_____________________2012 г.
		Проект защищен
		с оценкой (прописью, цифрой)
		___________________
		___________________2012 г.

 

 

 

 

 

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

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

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

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

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

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

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

 

 

 

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

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

 

УТВЕРЖДАЮ

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

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

___________   2012 г.

ЗАДАНИЕ

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

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

Группа 305

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

Вариант - 18

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

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

при условиях

,

где , , .

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

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

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

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

Пункт отправления	Пункты назначения					Запасы, ai (тонн)
	В1	B2	В3	B 4	B 5
A1	11	28	15	12	17	4
A2	32	27	26	10	3	6
Aз	12	4	22	3	1	10
A4	4	1	5	4	24	10
Потребности, bj (тонн)	7	7	7	7	2

 

 

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

 

Наименование разделов курсового проекта	Срок выполнения разделов проекта	Отметка о выполнении руководителя
Разработка графического метода решения задачи линейного программирования	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 представляют собой коэффициенты разложения этих векторов по векторам данного базиса.