Оптимизация доставки грузов и плана выпуска промышленной продукции
Решение транспортной задачи о доставке грузов методом потенциалов. Составление плана перевозок и перераспределение ресурсов. Формулировка экономико-математической модели задачи на максимум прибыли. Оптимизация плана выпуска промышленной продукции.
| Рубрика | Экономико-математическое моделирование |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 18.01.2012 |
| Размер файла | 213,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное государственное образовательное учреждение
высшего профессионального образования
Санкт-Петербургский государственный университет
водных коммуникаций
Кафедра математического моделирования и эконометрии
Курсовая работа
ОПТИМИЗАЦИЯ ДОСТАВКИ ГРУЗОВ И ПЛАНА ВЫПУСКА ПРОМЫШЛЕННОЙ ПРОДУКЦИИ
Выполнил:
студент группы ФЗО ЭУПП
Шеманенко Любовь
вар.40
Проверил: кандидат экономических наук
доцент Шилкина Ирина Дмитриевна
Санкт-Петербург
2011
СОДЕРЖАНИЕ
транспортная задача оптимизация
- 1. Оптимизация доставки грузов
- 1.1 Исходные данные
- 1.2 Формирование схемы движения
- 2. Оптимизация плана выпуска промышленной продукции
- 2.1 Исходные данные
- 2.2 Постановка задачи
- 2.3 Решение задачи симплекс методом
- 3. Выводы.
- 3.1 Транспортная задача
- 3.2 План выпуска промышленной продукции
- Список используемой литературы
1. Оптимизация доставки грузов
Задача, решаемая в данной работе, относится к классу оптимизационных, функционал которой имеет экстремум. Поиск экстремума заключается в выборе оптимального варианта из множества вариантов прикрепления пунктов отправления и назначения грузов. Предполагается, что на всех направлениях осуществляются перевозки однородного груза.
Необходимо решить задачу связи пунктов отправления и назначения, обеспечив вывоз всех грузов из пункта отправления, ввоз во все пункты назначения требуемых объемов грузов и достижения минимального суммарного грузооборота.
1.1 Исходные данные
Объемы отправления, тыс. тонн
Таблица 1
|
Пункты отправления |
Объём вывоза, тыс. тонн |
|
|
А |
475 |
|
|
Б |
490 |
|
|
Д |
270 |
Потребность в грузах, тыс. тонн
Таблица 2
|
Пункты назначения |
Объёмы ввоза, тыс. тонн |
|
|
Л |
390 |
|
|
М |
285 |
|
|
Н |
110 |
|
|
П |
180 |
|
|
С |
270 |
Расстояния между пунктами, км
Таблица 3
|
А-Л |
200 |
Б-Л |
190 |
Д-Л |
160 |
|
|
А-М |
185 |
Б-М |
85 |
Д-М |
100 |
|
|
А-Н |
200 |
Б-Н |
185 |
Д-Н |
145 |
|
|
А-П |
230 |
Б-П |
235 |
Д-П |
205 |
|
|
А-С |
195 |
Б-С |
175 |
Д-С |
220 |
1.2 Формирование схемы движения
Данная транспортная задача может быть решена методом потенциалов. Решается она на минимум грузооборота.
а) Целевая функция:
,
где - расстояние между i-м пунктом отправления и j-м пунктом назначения(км);
- объем перевозок между i-м пунктом отправления.
б) Ограничения:
1)
2) Все грузы из пунктов отправления должны быть отправлены:
для всех i от 1 до m,
где - объем отправления из i-го пункта;
i - индекс пункта отправления (i=1,…,m);
m - число пунктов отправления.
3) Все пункты назначения должны быть обеспечены грузами в плановом объеме:
для всех j от 1 до n,
где объем потребления в j-ом пункте;
j - индекс пункта назначения (j=1,…,n);
n - число пунктов назначения.
1.2.1 Составление начального плана перевозок
Для составления начального (опорного) плана перевозок воспользуемся методом северо-западного угла. По этому методу заполнение клеток начинается с левого верхнего угла, далее вправо и вниз.
Первую клетку заполняем, исходя из следующего условия:
; и т.д.
Для любого опорного плана число свободных клеток равно (m-1)(n-1). Число базисных переменных (заполненных клеток) должно быть равно n+m-1, среди них могут оказаться нулевые значения.
n=5; m=3заполненных клеток 7, пустых клеток 8
Таблица 4
|
Л |
М |
Н |
П |
С |
Qi |
ai |
||
|
А |
200 390 |
-185 85 |
200 |
+230 |
195 |
475 |
0 |
|
|
Б |
190 |
+85 200 |
185 110 |
-235 180 |
175 |
490 |
-100 |
|
|
Д |
160 0 |
100 |
145 |
205 |
220 270 |
270 |
-40 |
|
|
Vj |
390 |
285 |
110 |
180 |
270 |
|||
|
bj |
200 |
185 |
285 |
335 |
260 |
Значение целевой функции для начального плана перевозок:
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
Значения потенциалов определяются из условия, что для базисных (заполненных) клеток сумма потенциалов равна расстоянию Lij, т.е.
при этом потенциал первого пункта отправления принимается равным 0.
б) Проверяем условия оптимальности плана.
С целью проверки условий оптимальности плана для всех свободных клеток проверяется соотношение:
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
1.2.2 Перераспределение ресурсов
а) Строим в исходной матрице контур перераспределения ресурсов. Начало контура - клетка с максимальным нарушением условия оптимальности (клетка Х). В новом плане эта клетка из незаполненной становится заполненной. Далее строим замкнутый многоугольник с вершинами в загруженных клетках, за исключением начала контура. Число вершин контура должно быть четным. Половина из них загружается и помечается знаком «+», другая половина - разгружается и помечается знаком « - ». В каждой строке и в каждом столбце имеется две вершины.
В контуре допускаются только вертикальные и горизонтальные линии.
В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных Х ни одно из этих значений не должно превращаться в отрицательное число. Поэтому, с точки зрения переноса ресурсов по контуру анализируются только клетки, помеченные знаком « - », из них выбирается клетка с минимальным объемом перевозок, и этот объем переносится по контуру.
Таблица 5
|
Л |
М |
Н |
П |
С |
Qi |
ai |
||
|
А |
-200 390 |
185 |
200 |
+230 85 |
195 |
475 |
0 |
|
|
Б |
190 |
85 285 |
185 110 |
-235 95 |
+175 |
490 |
5 |
|
|
Д |
+160 0 |
100 |
145 |
205 |
-220 270 |
270 |
-40 |
|
|
Vj |
390 |
285 |
110 |
180 |
270 |
|||
|
bj |
200 |
80 |
180 |
230 |
260 |
Значение целевой функции для второго плана перевозок:
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj:
б) Проверяем условия оптимальности плана.
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
1.2.3 Перераспределение ресурсов
Клетка с максимальным нарушением условия оптимальности - Х
Таблица 6
|
Л |
М |
Н |
П |
С |
Qi |
ai |
||
|
А |
200 295 |
185 |
200 |
230 180 |
195 |
475 |
0 |
|
|
Б |
190 |
85 285 |
-185 110 |
235 |
+175 95 |
490 |
-85 |
|
|
Д |
160 95 |
100 |
+145 |
205 |
-220 175 |
270 |
-40 |
|
|
Vj |
390 |
285 |
110 |
180 |
270 |
|||
|
bj |
200 |
170 |
270 |
230 |
260 |
Значение целевой функции для третьего плана перевозок:
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
б) Проверяем условия оптимальности плана.
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
1.2.4 Перераспределение ресурсов
Клетка с максимальным нарушением условия оптимальности - Х
Таблица 7
|
Л |
М |
Н |
П |
С |
Qi |
ai |
||
|
А |
-200 295 |
185 |
200 |
230 180 |
+195 |
475 |
0 |
|
|
Б |
190 |
85 285 |
185 |
235 |
175 205 |
490 |
-85 |
|
|
Д |
+160 95 |
100 |
145 110 |
205 |
-220 65 |
270 |
-40 |
|
|
Vj |
390 |
285 |
110 |
180 |
270 |
|||
|
bj |
200 |
170 |
185 |
230 |
260 |
Значение целевой функции:
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
б) Проверяем условия оптимальности плана.
Условие оптимальности не выполняется, поэтому производим перераспределение объема перевозок.
1.2.5 Перераспределение ресурсов
Клетка с максимальным нарушением условия оптимальности - Х
Таблица 8
|
Л |
М |
Н |
П |
С |
Qi |
ai |
||
|
А |
200 230 |
185 |
200 |
230 180 |
195 65 |
475 |
0 |
|
|
Б |
190 |
85 285 |
185 |
235 |
175 205 |
490 |
-20 |
|
|
Д |
160 160 |
100 |
145 110 |
205 |
220 |
270 |
-40 |
|
|
Vj |
390 |
285 |
110 |
180 |
270 |
|||
|
bj |
200 |
105 |
185 |
230 |
195 |
Значение целевой функции:
а) Определяем потенциалы пунктов отправления ai и пунктов назначения bj
б) Проверяем условия оптимальности плана.
Условия оптимальности выполнены, т.е. данный план обеспечивает минимальный суммарный грузооборот.
Проверяем ограничения:
1)
2) Все грузы из пунктов отправления должны быть отправлены:
для всех i от 1 до m,
3) Все пункты назначения должны быть обеспечены грузами в плановом объеме:
для всех j от 1 до n,
Целевая функция:
Все ограничения соблюдены. Задача является закрытой. Мы выбрали оптимальный вариант из множества вариантов прикрепления пунктов отправления и назначения грузов, обеспечив вывоз всех грузов из пунктов отправления, ввоз во все пункты назначения требуемых объёмов грузов и достигли минимального суммарного грузооборота. Он оказался равным 201725 ткм, что на 31050 ткм меньше, чем при составлении начального плана перевозок. А это, соответственно, экономия денежных средств и рабочего времени для транспортной компании.
2. Оптимизация плана выпуска промышленной продукции
Задача: для выпуска четырех видов продукции требуются запасы сырья, рабочего времени и оборудования. Необходимо сформулировать экономико-математическую модель задачи на максимум прибыли найти оптимальный план выпуска продукции.
2.1 Исходные данные
Таблица 10
|
Тип ресурса |
Нормы затрат ресурсов на единицу продукции |
Запасы ресурсов |
||||
|
1 |
2 |
3 |
4 |
|||
|
Сырье |
5 |
3 |
2 |
4 |
60 |
|
|
Рабочее время |
20 |
13 |
18 |
30 |
450 |
|
|
Оборудование |
11 |
15 |
8 |
17 |
306 |
|
|
Прибыль на единицу продукции |
35 |
26 |
24 |
17 |
2.2 Постановка задачи
Искомые переменные:
Х - количество выпускаемой продукции первого вида;
Х - количество выпускаемой продукции второго вида;
Х - количество выпускаемой продукции третьего вида;
Х - количество выпускаемой продукции четвертого вида.
Целевая функция Z - максимизация прибыли от выпуска промышленной продукции.
Ограничения:
1.
2.
3.
4.
2.3 Решение задачи симплекс методом
Симплекс-метод позволяет решать задачи, в которых условия заданы величинами, имеющими разную размерность. Как и многие другие методы оптимизации, симплекс-метод основан на последовательном приближении к оптимальности. Процедура симплекс-метода содержит три элемента:
1) Указывается способ нахождения начального плана.
2) Устанавливается признак, дающий возможность проверить является ли данный план оптимальным.
3) Формируются правила, по которым неоптимальный план можно улучшить.
2.3.1 Составление начального плана
Так как в ограничениях нашей задачи левая часть меньше или равна правой, то неравенства мы преобразуем в равенства (кроме первого) путем добавления свободных переменных, коэффициент которых равен 1.
, Х - неиспользованное сырье;
, Х - неиспользованное время;
, Х - неиспользуемое оборудование.
С экономической точки зрения свободные переменные представляют собой неиспользованные ресурсы, поэтому их цена в целевой функции равна 0.
Коэффициенты при свободных переменных образуют единичную матрицу, определитель которой равен 1. Векторы, составленные из коэффициентов при свободных переменных образуют базис.
Представим первоначальное решение в табличной форме. Для этого построим первую симплекс-таблицу.
Таблица 11
|
Сj |
Базис |
Р0 |
35 |
26 |
24 |
17 |
0 |
0 |
0 |
|
|
Сi |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Х7 |
|||
|
0 |
Х5 |
60 |
5 |
3 |
2 |
4 |
1 |
0 |
0 |
|
|
0 |
Х6 |
450 |
20 |
13 |
18 |
30 |
0 |
1 |
0 |
|
|
0 |
Х7 |
306 |
11 |
15 |
8 |
17 |
0 |
0 |
1 |
|
|
Zj |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
Zj - Cj |
-35 |
-26 |
-24 |
-17 |
0 |
0 |
0 |
Zj - Cj - признак оптимальности в симплекс-таблице. Если задача решается на максимум, то план является оптимальным, если
Так как условия оптимальности нарушены, строим новую симплекс-таблицу.
2.3.2 Решение задачи
План 1
1) Определяем вектор (столбец), который вводится в базис. Это вектор с максимальным нарушением оптимальности (по модулю). Индекс ключевого столбца - k
ключевой столбец - X
2) Определяем вектор (строку), который выводится из базиса. Это строка, в которой имеет место соотношение:
,
где X - вектор решения;
X - число, стоящее на пересечении i-ой строки и ключевого столбца.
Индекс ключевой стоки - r. Элемент таблицы, находящийся на пересечении ключевого столбца и ключевой строки, называется генеральным, и обозначается X
ключевая строка - X
3) Рассчитываем новые значения вектора решений:
Правило 1: Для ключевой строки новое значение вектора решений не рассчитывается, а принимается, как значение И.
(см.правило1)
4) Определяем новые значения ключевой строки:
Правило 2: Каждый столбец, у которого на пересечении с ключевой строкой стоит 0, переписывается без изменений.
Правило 3: В новой симплекс-таблице значения элементов ключевого столбца будут равны 0, а на месте генерального элемента будет стоять 1.
Правило 4: Каждая строка, у которой на пересечении с ключевым столбцом стоит 0, переписывается без изменений.
(см.правило 3)
(см.правило 2)
(см.правило 2)
5) Находим значения остальных элементов новой симплекс-таблицы:
(см.правило2)
(см.правило2)
(см.правило2)
(см.правило2)
(см.правило 2)
(см.правило 2)
Таблица 12
|
Сj |
Базис |
Р0 |
35 |
26 |
24 |
17 |
0 |
0 |
0 |
|
|
Сi |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Х7 |
|||
|
35 |
Х1 |
12 |
1 |
0,6 |
0,4 |
0,8 |
0,2 |
0 |
0 |
|
|
0 |
Х6 |
210 |
0 |
1 |
10 |
14 |
-4 |
1 |
0 |
|
|
0 |
Х7 |
174 |
0 |
8,4 |
3,6 |
8,2 |
-2,2 |
0 |
1 |
|
|
Zj |
35 |
21 |
14 |
28 |
7 |
0 |
0 |
|||
|
Zj - Cj |
0 |
-5 |
-10 |
11 |
7 |
0 |
0 |
6) Определяем значения Z
Признак оптимальности нарушен!
План 2.
1) Ключевой столбец - X
2) ключевая строка - X
3) Рассчитываем новые значения вектора решений:
(см.правило1)
4) Определяем новые значения ключевой строки:
(см.правило 2)
(см.правило 3)
(см.правило 2)
5) Находим значения остальных элементов новой симплекс-таблицы:
(см.правило 2)
(см.правило 3)
(см.правило 2)
(см.правило 2)
(см.правило 3)
(см.правило 2)
Таблица 13
|
Сj |
Базис |
Р0 |
35 |
26 |
24 |
17 |
0 |
0 |
0 |
|
|
Сi |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Х7 |
|||
|
35 |
Х1 |
3,6 |
1 |
0,56 |
0 |
0,24 |
0,36 |
-0,04 |
0 |
|
|
24 |
Х3 |
21 |
0 |
0,1 |
1 |
1,4 |
-0,4 |
0,1 |
0 |
|
|
0 |
Х7 |
98,4 |
0 |
8,04 |
0 |
3,16 |
-0,76 |
-0,36 |
1 |
|
|
Zj |
35 |
22 |
24 |
42 |
3 |
1 |
0 |
|||
|
Zj - Cj |
0 |
-4 |
0 |
25 |
3 |
1 |
0 |
6) Определяем значения Z
Признак оптимальности нарушен!
План 3.
1) Ключевой столбец - X
2) ключевая строка - X
3) Рассчитываем новые значения вектора решений:
(см.правило1)
4) Определяем новые значения ключевой строки:
(см.правило 3)
(см.правило 2)
(см.правило 2)
5) Находим значения остальных элементов новой симплекс-таблицы:
(см.правило 3)
(см.правило 2)
(см.правило 2)
(см.правило 3)
(см.правило 2)
(см.правило 2)
Таблица 14
|
Сj |
Базис |
Р0 |
35 |
26 |
24 |
17 |
0 |
0 |
0 |
|
|
Сi |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Х7 |
|||
|
26 |
Х2 |
6,43 |
1,78 |
1 |
0 |
0,42 |
0,64 |
-0,07 |
0 |
|
|
24 |
Х3 |
20,36 |
-0,17 |
0 |
1 |
1,36 |
0,46 |
0,11 |
0 |
|
|
0 |
Х7 |
46,7 |
-14,35 |
0 |
0 |
-0,28 |
-5,92 |
0,21 |
1 |
|
|
Zj |
42,2 |
26 |
24 |
43,56 |
5,6 |
0,82 |
0 |
|||
|
Zj - Cj |
7,2 |
0 |
0 |
26,56 |
5,6 |
0,82 |
0 |
6) Определяем значения Z
Данный план оптимален!
Проверяем ограничения:
1.
2.
3.
4.
Итак, нарушений оптимальности нет, ограничения соблюдены. Задача является закрытой. Разработан оптимальный план выпуска промышленной продукции. В полученном плане необходимо изготовлять всего два вида продукции, при этом запасы сырья и рабочего времени использованы полностью, оборудование же осталось недоиспользованным. Мы получили максимально возможную прибыль, равную 655,82 у.д.е.
3. Выводы
3.1 Транспортная задача
В результате вычислений методом потенциалов мы выяснили, что оптимальный план выглядит следующим образом:
1. Из пункта отправления А груз доставляется в пункты назначения: Л - 230 т., П - 180 т.; С - 65 т.;
2. Из пункта отправления Б - в пункты назначения: М - 285 т.; С - 205 т.;
3. Из пункта отправления Д - в пункт назначения Л - 160 т.; Н - 110 т.
Именно таким образом мы достигаем минимального грузооборота, а именно определяем количество груза, перевозимого по маршрутам с наименьшими расстояниями между пунктами.
Данный план допустим, так как удовлетворяет всем ограничениям.
3.2 План выпуска промышленной продукции
В этой задаче мы нашли оптимальный план, при котором мы получим максимум прибыли при ограничении в ресурсах. Выглядит он следующим образом:
1. Продукция 2 - 6,43 единицы;
2. Продукция 3 - 20,36 единицы.
Продукция 1 и продукция 4 в наш план не входят, их выпуск нам не выгоден.
Обусловлен такой план соотношением между затратами ресурсов и прибылью на единицу продукции.
Данный план допустим, так как удовлетворяет всем ограничениям.
Список используемой литературы
1. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. 2001
2. Бабурин В.А., Бабурин Н.В. Управление грузовыми перевозками на водном транспорте. 2007
3. Шилкина И.Д., Полянская Т.И., Бурыкин А.А. Экономико-математические методы и модели. Оптимизация доставки грузов и плана выпуска промышленной продукции: методические указания по выполнению курсовой работы. 2008
Размещено на Allbest.ru
Подобные документы
Расчет связи пунктов отправления и назначения. Обеспечение вывоза всех грузов из пункта отправления и ввоза в места назначения необходимых объемов. Экономико-математическая модель задачи на максимум прибыли, расчет оптимального плана выпуска продукции.
курсовая работа [49,1 K], добавлен 29.07.2011Исследование методом Жордана-Гаусса системы линейных уравнений. Решение графическим и симплексным методом задач линейного программирования. Экономико-математическая модель задачи на максимум прибыли и нахождение оптимального плана выпуска продукции.
контрольная работа [177,8 K], добавлен 02.02.2010Экономико-математическая модель оптимального плана выпуска продукции. Оптимальная организация рекламной компании. Решение транспортной задачи: нахождение суммарных затрат на перевозку. Задача об оптимальном назначении (линейного программирования).
контрольная работа [812,0 K], добавлен 29.09.2010Нахождение начального опорного плана методом минимальной стоимости, оптимизация его методом потенциалов. Решение задачи о назначениях с заданной матрицей затрат. Построение набора дуг, соединяющих все вершины сети и имеющих минимальную протяженность.
контрольная работа [341,0 K], добавлен 24.04.2012Экономико-математическая модель прикрепления пунктов отправления к пунктам назначения, расчет оптимального плана перевозок. Решение транспортной задачи метолом потенциалов (перераспределение ресурсов по контуру), пример вычислительного алгоритма.
учебное пособие [316,8 K], добавлен 17.10.2010Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
дипломная работа [311,3 K], добавлен 17.01.2014Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Особенности построения опорных планов транспортной модели методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Оптимизация транспортной модели открытого и закрытого типа с помощью метода потенциала на основе опорного плана.
курсовая работа [68,6 K], добавлен 25.04.2014Определение наиболее выгодного суточного объема выпуска изделий, обеспечивающего максимум прибыли. Построение математической модели задачи, ее решение графическим методом и в среде MS Excel. Расчет диапазона дефицитности ресурсов и дрейфа оптимума.
контрольная работа [994,1 K], добавлен 16.02.2013Составление математической модели и решение задачи планирования выпуска продукции, обеспечивающего получение максимальной прибыли. Нахождение оптимального решения двойственной задачи с указанием дефицитной продукции при помощи теорем двойственности.
контрольная работа [232,3 K], добавлен 02.01.2012
