Оптимизация доставки грузов и план выпуска промышленной продукции

Введение
1. Постановка задачи и основные исходные данные
2. Формирование связей пунктов отправления и назначения
2.1. Формирование математической модели задачи
2.2. Оптимальное прикрепление пунктов отправления и назначения груза
3. Разработка оптимального плана выпуска продукции
3.1. Формирование математической модели задачи
3.2. Решение задачи оптимизации плана выпуска продукции симплекс-методом
Список литературы

Оптимизация доставки грузов и план выпуска промышленной продукции

Пункты отправ-ления
В1
В2
В3
В4
В5
А1
200
185
200
230 (190)
195
190
А2
20
190 (50)
85 (190)
185 (360)
235
175
600
А3
60
230 (315)
180
220
290 (265)
160 (400)
980
vj
170
65
165
230
100
Пункты назначения
365
190
360
455
400
Проделаем рассмотренную итерацию еще раз, введя перевозку из пункта отправления A2 в пункт назначения B4.
Рис. 2 Определение цикла
Таблица 8
План X2
Пункты отправ-ления
ui
Пункты назначения
Пункты отправ-ления
В1
В2
В3
В4
В5
А1
200
185
200
230 (190)
195
190
А2
5
190
85 (190)
185 (360)
235 (50)
175
600
А3
60
230 (365)
180
220
290 (215)
160 (400)
980
vj
170
80
180
230
100
Пункты назначения
365
190
360
455
400
Критерий оптимальности выполняется во всех клетках табл. 3.5, значит, план X2 является оптимальным.
Вычислим общий грузооборот:
(тыс. т.км.)
Оптимальный план перевозок:
.
Вывод: для оптимального грузооборота следует воспользоваться следующими перевозками:
Таблица 9
Пункт отправления
Пункт назначения
Длина пути, км
Объем груза, тыс. тонн
Грузооборот, тыс. т. км.
А
П
230
190
43 700
Д
М
85
190
16 150
Д
Н
185
360
66 600
Д
П
235
50
11 750
Е
Л
230
365
83 950
Е
П
290
215
62 350
Е
Р
160
400
64 000
3. Разработка оптимального плана выпуска продукции
3.1. Формирование математической модели задачи
Задача формируется следующим образом: для выпуска четырех видов продукции требуются затраты сырья, рабочего времени и оборудования. Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный план выпуска продукции.
Исходные данные, согласно варианту 37, представлены в табл. 10.
Таблица 10
Тип ресурса
Нормы затрат ресурсов на единицу продукции
Запасы ресурсов
1
2
3
4
Сырье
6
4
2
5
68
Рабочее время
23
15
18
32
470
Оборудование
12
14
8
17
300
Прибыль на единицу продукции
32
26
21
17
Требуется найти оптимальный план выпуска , где
- количество выпускаемой i-ой продукции (i=1,2,3,4), при котором суммарная прибыль будет максимальной.
Целевая функция – прибыль от продажи всей продукции:
.
Добавляются ограничения (по сырью, рабочему времени и оборудованию):
Естественное ограничение – неотрицательность всех переменных:
, i=1,2,3,4.
3.2. Решение задачи оптимизации плана выпуска продукции симплекс-методом
Переведем ограничения из неравенств в равенства. Для этого нужно к левым частям неравенств прибавить неотрицательные переменные , , . Задача примет вид:
Переменные , , образуют первоначальный базисный план.
Заполним первую симплекс-таблицу. Над заголовками переменных напишем коэффициенты целевой функции. В столбце «Базис» - переменные базисного плана. В столбец «БП» - «Базисный план» - правые части ограничений. В середине таблицы указываются коэффициенты системы ограничений. «ИС» – индексная строка. Она рассчитывается следующим образом: вектор коэффициентов целевой функции (вектор (0; 0; 0) – в данном случае) умножается скалярно на вектор-столбец xi (например, x1=(6; 23; 12) и из полученного произведения вычитается коэффициент целевой функции при xi. Например, под столбцом x1 получим: 0*6+0*23+0*12-32=-32.
Таблица 11
Шаг 0
32
26
21
17
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x5
68
6
4
2
5
1
x6
470
23
15
18
32
1
x7
300
12
14
8
17
1
ИС
-32
-26
-21
-17
Выбираем наименьшее значение ИС. В данном случае наименьшим является –32. Значит, отмечаем столбец x1. Рассчитываем ключевое соотношение (отношение элементов «БП» к элементам «x1»): . Значит, нужно выбрать строку x5. На пересечении выделенных строки и столбца находится ключевой элемент, равный 6. В новой таблице на месте переменной x5 будет стоять x1.
Для того, чтобы заполнить следующую таблицу, нужно выделенную строку разделить на ключевой элемент (т.е. на 6), значения в остальных ячейках таблицы определяются методом прямоугольника.
Он заключается в следующем: из каждого элемента предыдущей таблицы нужно вычесть произведение значений выделенных строк и столбца, на которые опущен перпендикуляр из этого элемента, деленное на ключевой элемент.
Например, на месте выделенного зеленого значения будет следующее: .
Шаг 1
32
26
21
17
Базис
БП
x 1
x 2
x 3
x 4
x 5
x 6
x 7
x1
34/3
1
2/3
1/3
5/6
1/6
x6