ГОТОВЫЕ ДИПЛОМНЫЕ РАБОТЫ, КУРСОВЫЕ РАБОТЫ, ДИССЕРТАЦИИ И РЕФЕРАТЫ
Оптимизация с использованием модели транспортной задачи. | |
Автор | Ольга |
Вуз (город) | МИИГАиК (г.Москва) |
Количество страниц | 36 |
Год сдачи | 2009 |
Стоимость (руб.) | 1000 |
Содержание | Введение………………........…………………………………………………….
1 Оптимизация с использованием модели транспортной задачи ……............. 1.1 Математическая модель задачи……...........…………………..………….…. 1.2 Выбор и описания метода решения………...........………………………… 1.3 Оптимизация решения вручную…………………...............………………. 1.4 Оптимизация решения с использованием средств Microsoft Excel ……… 2. Задача о назначениях………………………………………………………. 2.1. Математическая модель задачи ………………………………………. 2.2. Выбор и описания метода решения………...........………………………… 2.3. Оптимизация решения вручную…………………...............………………. 2.4. Оптимизация решения с использованием средств Microsoft Excel ……. 2.5. Оценка эффективности оптимального решения …………………………. 3. Общая задача линейного программирования …………………………….... 3.1. Математическая модель задачи………………………………….. 3.2. Выбор и описание метода решения…………………………... … 3.3. Оптимизация решения вручную…………………………………. 3.4 Оптимизация решения с использованием средств Microsoft Excel ….…... 3.5 Оценка эффективности оптимального решения ……………………... 4. Использование методов теории массового обслуживания 4.1. Описание объекта и математическая модель задачи ………………….. 4.2. Выбор и описание метода решения ……………………………………. 4.3. Решение задачи и его интерпретация………………………………. 4.4. Оценка эффективности оптимального решения …………………….. Заключение ………………………………………………………………………. Литература ……………………………………………. |
Список литературы | Литература:
1. Экономико-математические методы и модели для руководителя. Под ред. Сергеева - М.: «Экономика»,1984. 2. Кузнецов А.В., Холодов Н.И. Математическое программирование. – Мн.: Выш. Шк., 1984 – 256 с. 3. Кузнецов А.В., Сакович В.А., Холодов Н.И. Высшая математика: Математическое программирование. – Мн.: Выш. Шк., 1994 – 350 с. 4. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965 – 323 с. 5. Системный анализ и исследование операций. Методические указания к курсовой работе для специальности 1-53.01.02.ПЗ - “Автоматизированные системы обработки информации”. Могилев: ММИ, 1996. 30 с. 6. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г. 7. Б. В. Гнеденко, И. Н. Коваленко. Введение в теорию массового обслуживания. М., 1987. 8. Т. Л. Саати. Элементы теории массового обслуживания и ее приложения: Пер. с англ. /Под. ред. И. Н. Коваленко, изд-ие 2. М., 1971. |
Выдержка из работы | Введение
В настоящее время задачи, стоящие в народном хозяйстве планирование производства, обслуживания, транспортных перевозок и т.п., являются очень сложными и объемными. Каждая такая задача имеет множество параметров, от которых зависит эффективность тех или иных операций. Если еще в начале двадцатого века задачи производственного планирования можно было решить методом перебора вариантов, то сейчас это невозможно. Поэтому и возникла дисциплина, получившая название “Системный анализ и исследование операций”. Под исследованием операций понимается применение количественных математических методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Исследование операций начинается в том случае, когда для принятия количественного решения применяются математические методы. В настоящей работе производится решение комплекса типовых оптимизационных задач, стоящих перед руководителем предприятия или его подразделения. Это задача о наиболее выгодном распределении ресурсов, выпуске и транспортировке продукции, задача о назначениях, задача линейного программирования и задача с использованием системы массового обслуживания. 1 Оптимизация с использованием модели транспортной задачи 1.1 Математическая модель задачи Математическая модель задачи представляет собой следующее. Необходимо доставить от заводов i некоторый однородный товар в объеме Аi единиц потребителям j с минимальными транспортными издержками. Потребность каждого потребителя в товаре составляет Вj единиц. Известны также сij – величины стоимости перевозки единицы груза от i – того завода к j – потребителю. Т.к. , то мы имеем транспортную задачу открытого типа. Введем переменные xij=Аij, обозначающие количество единиц груза, перевозимого от i-го завода j-му потребителю. Такие переменные должны удовлетворять следующим условиям: 1. ограничение по запасам: j=1n xij = Ai; (1.1.1) 2. ограничение по потребностям: i=1m xij = Bj; (1.1.2) 3. условия неотрицательности: xij0(i=1..m; j=1..n). (1.1.3) Суммарные транспортные затраты на перевозки определяются следующей формулой: L =i=1m j=1n cijxij (1.1.4) Таким образом, математически транспортная задача представляется так. Найти m.n переменных xij, удовлетворяющих системам уравнений (1.1.1) и (1.1.2), и условиям неотрицательности (1.1.3), для которых целевая функция (1.1.4) принимает минимальное значение. 1.2 Выбор и описание метода решения Прежде чем приступить к решению задачи необходимо построить исходный опорный план. Для этого воспользуемся методом минимальной стоимости. В таблице из всех значений выбираем наименьшее и в клетку (i,j) с наименьшей стоимостью записываем меньшее из чисел Аi и Bj (объемы поставок и потребностей соответственно). Исключаем из рассмотрения строку i, если запас Аi вывезен полностью, или столбец j, если потребность Bj полностью удовлетворена. Среди остальных стоимостей снова выбираем наименьшую и заполняем соответствующую клетку таблицы. Таким же образом продолжаем заполнять клетки таблицы, пока не будет найдено опорное решение. Для решения воспользуемся методом потенциалов. Теорема: Решение транспортной задачи будет оптимальным, если найдутся такие числа и , называемые соответственно потенциалами поставщиков и потребителей, которые будут удовлетворять условиям: + =сij для ; (1.2.1) + =0). если для всех клеток это условие выполнено, то опорный план является оптимальным (решение завершено). Если же для некоторых свободных клеток sij < 0, то клетка с наименьшим значением sij является ерспективной и выполняется следующий пункт алгоритма. 2.3. К перспективной клетке сроится цикл, расставляются знаки по циклу, при этом в перспективную клетку ставится +, а остальные знаки в вершинах цикла чередуются, и определяется величина перераспределения груза Qij = min xij, где xij – объем перевозки груза, записанный в клетках (вершинах) цикла таблицы, отмеченных знаком минус. 2.4. осуществляется перераспределение груза по циклу на величину Q. В результате выполнения этого пункта будет получен новый опорный план, которй проверяется на оптимальность, т.е. производится переход к пункту 2.1 алгоритма. После перераспределения потенциалы пересчитываются. 1.3 Оптимизация решения вручную Составим исходный опорный план по методу “минимального элемента”. Т.к. при таких начальных условиях Ai < Bj , то мы имеем транспортную задачу с неправильным балансом. Рассмотрим первый вариант( расширим мощность первого завода с дополнительными затратами на производство единицы продукции ). Таблица 1.1 – Транспортная таблица B1 B2 B3 B4 ai αi A1 4 4 6 5 7 7 4 9 300+150 0 350+ 100- A2 7 7 9 4 10 9 7 7 600 3 150- + 450 A3 0 8 2 2 3 3 0 8 1000 -4 700- 300+ bj 500 700 400 450 βj 4 6 7 4 Найдем значения потенциалов из следующей системы уравнений 1+1=4; 2+1=7; 2+4=7; 1+3=7; 3+2=2 Получаем: 1=0; 2=3;3=-4; 1=4; 2=6; 3=7; 4=4. Псевдостоимости меньше стоимостей. Т.к. задача на минимум, то оптимальный план достигнут. Получили следующее: Таблица 1.2 – Транспортная таблица B1 B2 B3 B4 ai αi A1 4 4 1 5 2 7 4 9 300+150 0 450 A2 7 7 4 4 5 9 7 7 600 3 50 100 450 A3 5 8 2 2 3 3 5 8 1000 1 600 400 bj 500 700 400 450 βj 4 1 2 4 1+1=4;2+1=7;2+2=4;2+4=7;3+2=2;3+3=3. 1=0;2=3;3=1;1=4;2=1;3=2;4=4. Стоимость перевозок: 4*450+7*50+100*4+7*450+2*600+3*400=6480. Затраты на производство: (300*7+150*(7+2))+(600*6)+2000=9050. Рассмотрим второй вариант( расширим мощность второго завода с дополнительными затратами на производство единицы продукции ). Таблица 1.3 – Транспортная таблица B1 B2 B3 B4 ai αi A1 4 4 6 5 7 7 4 9 300 0 300 A2 7 7 9 4 10 9 7 7 600+150 3 200 100 450 A3 0 8 2 2 3 3 0 8 1000 1 600 400 bj 500 700 400 450 βj 4 1 2 4 1+1=4;2+1=7;2+2=4;2+4=7;3+2=2;3+3=3. 1=0;2=3;3=1;1=4;2=1;3=2;4=4. Стоимость перевозок: 4*300+7*200+100*4+7*450+2*600+3*400=8550. Затраты на производство: 2100+(600*6+150*(6+6))+2000=9500. Рассмотрим третий вариант(добавим четвертый завод с затратами на производство единицы продукции ). Решение представлено в таблицах 4-6. Таблица 1.4 – Транспортная таблица B1 B2 B3 B4 ai αi A1 4 4 6 5 7 7 4 9 300 0 200+ 100- A2 7 7 9 4 10 9 7 7 600 3 300- 300+ A3 0 8 2 2 3 3 0 8 1000 -4 700 300 А4 15 12 17 15 18 8 15 15 150 11 + 150- bj 500 700 400 450 βj 4 6 7 4 |