Автор работы: Пользователь скрыл имя, 29 Апреля 2013 в 21:45, курсовая работа
Целью данной курсовой работы является изучение методов решения задач математического моделирования на примере задач планирования производства и транспортной задачи.
Задачи работы:
изучить литературу по данной теме
для заданного варианта получить решение задачи линейного программирования:
- графическим методом;
ВВЕДЕНИЕ 4
1 ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ К РЕШЕНИЮ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 5
1.1 Определение и характеристика линейного программирования 5
1.2 Характеристика геометрического метода решения задач 7
1.3 Характеристика симплекс-метода как основного аппарата решения задач линейного программирования 10
1.4 Характеристика метода решения задач с помощью теории двойственности 14
1.5 Основные этапы, особенности и методы решения транспортной задачи 16
2 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 20
2.1 Решение задачи планирования производства геометрическим способом 20
2.2 Решение задачи планирования производства симплекс-методом 25
2.3. Решение задачи планирования производства с помощью теории двойственности 30
2.4 Составление математической модели транспортной задачи 31
2.5 Нахождение опорного плана транспортной задачи методом наименьшего элемента 32
2.6 Решение транспортной задачи методом потенциалов 36
ЗАКЛЮЧЕНИЕ 38
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 39
Рассмотрим порядок работы с симплекс таблицей.
Первая симплекс-таблица подвергается преобразованию, суть которого заключается в переходе к новому опорному решению.
Алгоритм перехода к следующей таблице такой:
В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.
Следует просмотреть строку целевой функции (индексную), если в ней нет отрицательных значений (в задачи на нахождение максимального значения), либо положительных (в задачи на нахождение минимального значения) кроме стоящего на месте Y0 (свободного столбца), то значит, что оптимальное решение получено. В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму [6].
Имеется т видов сырья в количестве b1, b2,..., bт, которые используются для изготовления п видов продукции. Известно: аij — расход i-го вида сырья на единицу j-ой продукции; сj. — прибыль при реализации единицы j-го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль.
Математическая модель данной задачи имеет вид:
F(X) = с1 х1 + с2 х2 + ... + сп хп→max, (11)
(12)
где х j, j = 1,2, ..., п — объем производства j-го вида продукции.
Предположим, что второй производитель хочет перекупить сырье. Составим двойственную задачу, решение которой позволит определить условия продажи сырья. Введем вектор оценок (цен) видов сырья Y=(у1, у2,… …,ут). Затраты на приобретение i -го вида сырья в количестве bi равны biуi . Второму производителю выгодно минимизировать суммарные затраты на приобретение всех видов сырья, поэтому целевая функция имеет вид
Z(Y) =b1у1 +b2у2 +…+bтут→ min (13)
Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j-й продукции, т.е. а1j у1 + а2j у2 +…+ аmj ут, меньше прибыли сj получаемой при реализации этого изделия. Система ограничений задачи имеет вид
(14)
Оценки видов сырья должны удовлетворять условиям неотрицательности уi ≥0, i = 1, 2, …, т.
Таким образом, связь исходной и двойственной задач состоит в том, что коэффициенты cj целевой функции исходной задачи являются свободными членами системы ограничений двойственной задачи, cвoбодные члены bi системы ограничений исходной задачи служат коэффициентами целевой функции двойственной задачи, а матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи.
Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение [8].
Предположим что на три базы , , поступил однородный груз в количествах: соответственно. Груз требуется развезти в пять пунктов: в пункт в пункт в пункт в пункт в пункт
Таблица 1.5.1
Пункт направления |
B1 |
B2 |
B3 |
B4 |
B5 |
Запасы, ai |
A1 |
c11 |
c12 |
c13 |
c14 |
c15 |
A1 |
A2 |
c21 |
c22 |
c23 |
c24 |
c25 |
A2 |
A3 |
c31 |
c32 |
c33 |
c34 |
c35 |
A3 |
Потребности, bj |
b1 |
b2 |
b3 |
b4 |
b5 |
|
Составим математическую модель данной задачи:
Целевая функция:
(15)
+
Ограничения:
где хij – количество груза, отправляемого с базы Ai в пункт Bj.
Одним из способов решения транспортных задач является метод северо-западного угла. На каждом этапе метода максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение происходит таким образом, что полностью выносится груз из или полностью удовлетворяется потребность [9].
Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.
Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij ≥ 0, а в маленькие клетки – соответствующие тарифы Cij [9].
Таблица 1.5.2
Затем решение задачи разбивается на два этапа:
1) Метод северо-западного угла
Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Хij горизонтальным и вертикальным уравнениям.
2) Метод наименьшего элемента
Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них.
В остальном действуют аналогично предыдущему способу.
3) Метод потенциалов
Соотношения определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному присваивают произвольное значение (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.
Если известны
потенциалы решения Х0 транспортной
задачи и для всех незаполненных
ячеек выполняются условия αi+β
Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.
Цикл перерасчёта
таблицы – это
– Одна ячейка пустая, все остальные занятые.
– Любые две соседние ячейки находятся в одной строке или в одном столбце.
– Никакие три соседние ячейки не могут быть в одной строке или в одном столбце.
– Пустой ячейке присваивают знак "+", остальным – знаки "–" и "+".
Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой αr+βs > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:
– В плюсовых клетках добавляем Х.
– Из минусовых клеток вычитаем Х.
– Все остальные клетки вне цикла остаются без изменения.
Получим новую таблицу, дающую новое решение Х, такое, что
F (X1) ≤ F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует [10].
Трудность построения математической модели заключается в идентификации переменных и последующем представлении цели и ограничений в виде математических функций этих переменных. Если модель содержит только две переменные, то задачу линейного программирования можно решить графически. В случае трёх переменных графическое решение становится менее наглядным, а при большем значении переменных – даже невозможным. Однако графическое решение позволяет сделать выводы, которые служат основой для разработки общего метода решения задачи линейного программирования.
Запишем условия задачи. Предприятие предполагает выпускать два вида продукции А1 и А2, для производства которых используется сырьё трех видов. Производство обеспечено сырьем каждого вида в количествах: 600, 357, 600 кг. На изготовление единицы изделия А1 требуется затратить сырья каждого вида 3, 3, 1 кг, соответственно, а для единицы изделия А2 - 4, 1, 5 кг. Прибыль от реализации единицы изделия А1 составляет 42 ден.ед., для единицы изделия А2 - 26 ден.ед.
Требуется составить план производства изделий А1 и А2 обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.
Занесём необходимые нам данные во вспомогательную таблицу:
Таблица 2.1.1
Вид сырья |
Продукция |
Ограничения по сырью | |
А1 |
А2 | ||
1-й |
3 |
4 |
600 |
2-й |
3 |
1 |
357 |
3-й |
1 |
5 |
600 |
прибыль |
42 |
26 |
Информация о работе Решение задач с помощью линейного программирования