">
Математика Математический анализ
Информация о работе

Тема: Использование математических методов при решении отдельных задач линейного программирования

Описание: Графический и симплекс-метод решения задач линейного программирования. Решение двойственных задач. Транспортная задача. Задачи с несколькими целевыми функциями Задачи с несколькими целевыми функциями, целочисленного программирования, дробно-линейного программирования.
Предмет: Математика.
Дисциплина: Математический анализ.
Тип: Курсовая работа
Дата: 15.08.2012 г.
Язык: Русский
Скачиваний: 8
Поднять уникальность

Похожие работы:

Министерство образования и науки Самарской области

ГБОУ СПО Тольяттинский социально-экономический колледж

Курсовая работа

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

На тему: «Использование математических методов при решении отдельных задач линейного программирования».

           

2012

Содержание

Введение…………………………………………………………………………….

1.Решение задач линейного программирования…………………………………

Графический метод решения задач линейного программирования………

Симплекс-метод решения задач линейного программирования…………

Решение двойственных задач………………………………………………

Транспортная задача…………………………………………………………

Задача о назначениях………………………………………………………..

2.Решение специальных задач программирования……………………………...

Задачи с несколькими целевыми функциями……………………………..

Задачи целочисленного программирования………………………………

Задачи дробно-линейного программирования……………………………

Задачи параметрического программирования……………………………

Решение задачи теории игр……………………………………………………

Сетевое моделирование……………………………………………………….

Заключение……………………………………………………………………….

Список литературы……………………………………………………………….

Приложения……………………………………………………………………….

ВВЕДЕНИЕ

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

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

Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

Задачи курсовой работы:

изучение различных методов решения экстремальных задач;

применение полученных знаний на практике.

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Графический метод решения задач линейного программирования

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

Графический метод включает в себя два этапа:

отыскание области допустимости решений;

отыскание оптимальных решений или указание, что их нет.











 

  0 1   1 0   

  0 -1   1 0    

 



 



  6   6  





A* 





A*(4; )

B* 





B*(0; )





Ответ: 

Предмет исследования задачи вопросы рассматриваются в курсовой и выводятся в формуле.



Симплекс-метод решения задач линейного программирования

Алгоритм симплекс метода:

приведение задачи к канонической формуле записи;

определение базисных переменных и исходного базисного решения;

построение симплексной таблицы.

Базис -1 0 … cj …   С B …  …  … … …  …   xi ci bi … aij …  … … …  …     fi … j   xi – базисные переменные.

cj –коэффициенты перед базисными переменными целевой функции.

bi – значение базисных переменных.

xj– свободная переменная.

ci – коэффициенты перед свободными переменными в ограничениях первой группы.

fi – значение целевой функции в базисном решение на каждой итерацией.

?– показывает, что в строке находятся со значком

j – относительные оценки которые подсчитываются только для свободных переменных по формуле: 

J – множество индексов базисных переменных.

Проверка базисного решения на оптимальную по критерию оптимальность симплекс-метода.

Для того чтобы базисное решение было оптимальным необходимо и достаточно выполнение условий:

относительные оценки ?0;

в составе базисных переменных отсутствуют искусственные переменные.

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

Если хотя бы одна относительная оценка меньше 0 происходит пересчет симплексной таблицы.

Определение переменной, которая войдёт в базис.

xk / |k| = max {|j|}

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

Определение переменной, которая покинет базис.

min{bi/aik}

Строка, соответствующая переменной, которая покинет базис, называется главной строкой. Элемент, стоящий на пересечении главной строки и столбца так же называется главной.

Пересчет симплексной таблицы.

Главный элемент заменяется взаимно обратным числом.

Все остальные элементы пересчитываются по правилу прямоугольника.











Приведение задачи к канонической форме записи.











ИБР: 

БП: 

Построение симплексной таблицы Базис -1 0 1 -1   C B     0 -2 -2 1   0 2 1 -2   0 5 1 1   ? 0 -1 1  Y={3,4,5}



 Базис -1 0 0 -1   C B     0 6 2 -3   1 2 -1 2   0 3 -1 3   ? 2 1 -1  











Базис -1 0 0 0   C B     0 9 1 1   1 0     -1 1     ? 3    









=>БР: 



Ответ: 

Решение двойственных задач

Правило построения двойственных задач

Теория двойственности предназначена для решения отдельных задач для линейного программирования, а именно в случаях:

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

Необходимость введения искусственных переменных

Для любой задачи линейного программирования может быть построена по определенным правилам другая задача, называемая двойственной, причем исходная и двойственная задача составляет пару взаимодвойственных задач. Исходная задача Двойственная задача  1 2  F(x)->max

Количество ограничений первой группы (m)

“<=”; “=”

Правильные части ограничения 1-й группы (bi)

Количество аргументов целевой функции

Xj, j=1,n

Xj>=0

Xj - неограниченно по знаку

Cj – коэффициент передачи xj в целевой функции

А Z(y)->min

Количество аргументов

Yi=1,m

Yi>=0

Yi – не ограничено по знаку

Коэффициент передачи yi в целевой функции

Количество ограничений первой группы

“>=”, “=”

Правые части ограничений первой группы

  Для построения двойственной задачи исходная задача должна быть готова к построению.

Теорема двойственности Исходная задача Двойственная задача  1 2  



 



  Теорема первая: если одна из пары взаимодвойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем f*=z*

Теорема вторая (критерий разрешимости двойственных задач): для того, чтобы каждая из пары взаимодвойственных задач была разрешима необходимо и достаточно выполнение двух условий.



Если 







































Ответ: 

Транспортная задача

Пусть имеется M-поставщиков некоторого однородного груза.

Ai, i=1,m – количество груза, имеющегося у i-го поставщика

B1, B2,…, Bn, n - количество потребителей данного груза

Bj, j=1,n – количество грузов, в котором нуждается j-ый потребитель.

i=1,m

(c I j) - стоимость i-го поставщика j-го груза.

J=1,n

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

Выбор объекта исследования – план доставки груза от поставщиков к потребителю.

Цель – планирование доставки груза

Стоимость перевозки всего груза наименьшая













Транспортная задача называется сбалансированной, если количество грузов у поставщиков равно количеству груза, в котором нуждаются потребители.

Решение транспортной задачи методом потенциалов требует двух подготовительных этапов:

Приведение задачи к канонической форме записи

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

Говорят, что транспортные задачи представлены в канонической форме записи, если задача сбалансированная. В таком случае в модель вводят фиктивного потребителя.





Исходный план строится с помощью двух методов:

Метод северо-западного угла

Метод минимального элемента

Между первым и вторым подготовительными этапами строится исходная транспортная таблица. Aii B1 B2 … Bn  A1 C11 C12 … Cm  A2 C21 C22 … C2n  … … … … …  am Cm1 Cm2 … cmn  Критерий разрешимости транспортной задачи: для того, чтобы транспортная задача была разрешима необходимо и достаточно, чтобы она была сбалансирована.

Метод северо-западного угла (всегда заполняется левая верхняя клетка, а в методе минимального элемента – клетка с наименьшим Cij).

Правило заполнения клетки:



Aibjai=bj

Xij=ajxij=bjxij=ai=bj

Удал. i-ая строкаудал. J-ый столбецудал. I-ая строка и j-ый столбец ai bj 10 8 7  11 8 6 5  14 4 5 7  Привести к канонической форме записи:







ai bj  8 7  1 10    14      ai bj  7    10 1         ai bj      10 1   7  7    ai bj      10 1     7 7  БП: x11, x12, x22, x23.

ИП: x11=10; x12=1; x13=0; x21=0; x22=7; x23=7.

F0=80+6+35+49=170

Проверка правильности построения исходного плана:

Груз должен быть вывезен

Потребности в грузе должны быть удовлетворены

Количество базисных переменных должно быть m+n-1

Никакие 4 базисные переменные не должны составлять прямоугольник Ai хранилища элеватор 60 60 60  50 50 |2 3 2  70 10 |2 60 |4 5  60 6 5 60 |7  F0=10020+240+420=780

Метода наименьшего элемента ai bj 10 8 7  11 8 6 5  14 4 5 7   ai bj  8 7  11 8 6 5  14 10 |4 5 7   ai bj      8 4 |6 7 |5   10 |4 4 |5 7  БП: x12, x13, x21, x22.

ИП: x11=0; x12=4; x13=7; x21=10; x22=4; x23=0

f0=119

Задача о назначениях

Объект исследования: штатное расписание

Цель: планирование заданного расписания

Критерий: наименьшее время выполнения всего объема работ

0, если работник не назначен на j-ю работу

Xij=

1, если работник назначен на j-ю работу

F(x)=



 ai bi 1 2 … N  1 T11 T12 … T1n  2 T21 T22 … T2n  … … … … …  m Tm1 Tm2 … Tmn  Особенность аргументов целевой функции приводит к решению задачи о назначении венгерским методом.

Алгоритм:

Приведение задачи к канонической форме записи: говорят, что задача приведена к канонической форме записи, если она сбалансирована. Задача о назначении называется сбалансированной, если количество работников равно количеству рабочих мест (если она не сбалансирована, то вводятся фиктивные работники или рабочие места).

Построение исходного плана

2919173210

2516151413

T=2517182315

3015201914

2720222512

5 менеджеров

=>

5 цехов

Из элементов строк вычесть наименьшее в строке число 29 19 17 32 10 10  25 16 15 14 13 13  25 17 18 23 15 15  30 15 20 19 14 14  27 20 22 25 12 12   19 9 7 22 0  12 3 2 1 0  10 2 3 8 0  16 1 6 5 0  15 8 10 13 0  101210 9 8 5 21 0  2 2 0 0 0  0 1 1 7 0  6 0 4 4 0  5 7 8 12 0  0 – возможность назначения

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

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

Критерии оптимальности венгерского метода

Количество линий равно порядку матрицыКоличество линий меньше порядка матрицы

X* Пересчет

Ответ

Пересчет – главный элемент это наименьшее число из не вычеркнутых. Не вычеркнутые числа уменьшаются на главный элемент, те, которые вычеркнуты дважды, увеличиваются на главный элемент, вычеркнутые один раз не изменяются. 4 3 0 16 0  2 2 0 0 5  0 1 1 7 5  6 0 4 4 5  0 2 3 7 0  5=5-> план является оптимальным

4-й менеджер назначен во 2-й цех

4  0 16 0  2  0 0 5  0  1 7 5        0  3 7 0  2-й менеджер назначен в 4-й цех 4  0  0      5  0  1  5        0  3  0  1-й менеджер назначен в 3-й цех            0  1  5        0  3  0  5-й менеджер назначен в 5-й цех

Ответ:

00100

00010

X*=10000

01000

00001

F min=17+14+25+15+12=83

РЕШЕНИЕ СПЕЦИАЛЬНЫХ ЗАДАЧ ПРОГРАММИРОВАНИЯ

Задача с несколькими целевыми функциями

Общая задача линейного программирования с двумя целевыми функциями имеет следующий вид:









Ответ: