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

Информация » Оптимизация в планировании перевозок » Оптимизация распределения подвижного состава по маршрутам перевозок грузов

Страница 2

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

При решении задач симплекс-методом все неравенства (1) необходимо обратить в равенства. Для этого введем свободные переменные х1, х2, …,х6 ≥ 0.

Тогда

х11+х21+х31+х41+х1=10

х12+х22+х23+х42 +х2=15

14х11+15х12+х3=150

7х21+5х22+х4= 100(3)

15х31+17х32 +х5=200

9х41+9х42+х6=250

Qmax=14х11+15х12+7х21+5х22+15х31+17х32+9х41+0х1+0х2+0х3+0х4+0х5+0х6 ® max. (4)

Свободные переменные х1 и х2 выражают количество неиспользованных автомобилей из числа имеющихся, а х3, …, х6 – объем неперевезённого груза. В целевую функцию они входят с коэффициентами, равными нулю.

Все данные полученных уравнений заносятся в специальную симплекс-таблицу (таблица 2).

Каждая строка в симплекс-таблице отражает по порядку все ранее написанные уравнения, а по столбцам таблицы располагаются коэффициенты, с которыми переменные (х11, х12, …, х6) входят в соответствующее уравнение. Если какая-либо переменная не входит в рассматриваемое уравнение, то в таблице для нее проставляется нуль. В индексной строке записываются коэффициенты при соответствующей переменной в выражении целевой функции с обратным знаком.

Алгоритм вычислений симплекс-методом состоит в следующем.

Шаг 1. Выбираем в индексной строке наибольшее отрицательное число. Ему соответствует ключевой столбец. В таблице 2 это столбец х32 с числом 17.

Шаг 2. Определяем ключевую строку. Для этого разделим числа столбца свободных членов на соответствующие им положительные числа ключевого столбца: 10/0 = ∞; 15/1 = 15; 150/0= ∞; 200/17 = 11,76; 250/0 = ∞. Из всех полученных частных выбираем наименьшее (200/17 = 11,76). Оно определяет ключевую строку.

На пересечении ключевой строки и ключевого столбца находится ключевое число (17).

Шаг 3. Переходим к построению следующей симплекс-таблицы, в которой в первую очередь заполняется главная строка. Главная строка располагается там, где в предыдущей симплекс-таблице находилась ключевая строка, а числа главной строки определяются путем деления чисел ключевой строки на ключевое число. Вместо прежнего переменного в столбце переменных записывается переменное соответствующего ключевого столбца. Поэтому для главной строки таблицы 3 в столбце переменных указано 11,76.

В том столбце, который в предыдущей таблице был ключевым, все клетки заполняются нулями, за исключением клетки, где находилось ключевое число. Там всегда будем иметь 1 по расчету чисел главной строки. Те столбцы, у которых в клетках ключевой строки (см. табл. 2) записаны нули, переписываются без изменений. Аналогично правило и для строк. Если в ключевом столбце строке соответствует нуль, то она переписывается в следующую таблицу без изменений.

Для остальных клеток (в столбце свободных членов клетка строки х2, х3, х2, х5, х2 и в индексной строке клетка столбца х32) определяются производные числа (Пр) по правилу:

Пр = Вч – КсКст/Кч,

где Вч – выбранное число;

Кс – соответствующее число в ключевой строке;

Кст – соответствующее число в ключевом столбце;

Кч – ключевое число.

Теперь известны все числа, и построение симплекс-таблицы (см. табл. 2) закончено. Так как в индексной строке еще сохранились отрицательные числа, то решение продолжается, повторяются все операции, описанные выше. Вычисления проводятся до той поры, пока в индексной строке одной из таблиц не окажутся числа больше или равные нулю. Опуская промежуточные решения, покажем сразу матрицу оптимального распределения (таблица 4).

В заключение можно отметить, что изложенным методом можно решать и другие задачи. Например, можно определить минимальное число автомобилей, необходимое для перевозки запланированного количества грузов. Для этого нужно отбросить ограничения по количеству автомобилей и ввести расчет по изложенной схеме до тех пор, пока не будет вывезен весь запланированный груз.

Исходная симплекс-таблица Таблица 2

Столбец переменных

Столбец свободных членов

Строка переменных

Х11

Х12

Х21

Х22

Х31

Х32

Х41

Х42

Х1

Х2

Х3

Х4

Х5

Х6

Х1

10

1

0

1

0

1

0

1

0

1

0

0

0

0

0

Х2

15

0

1

0

1

0

1

0

1

0

1

0

0

0

0

Х3

150

14

15

0

0

0

0

0

0

0

0

1

0

0

0

Х4

100

0

0

7

5

0

0

0

0

0

0

0

1

0

0

Х5

200

0

0

0

0

15

17

0

0

0

0

0

0

1

0

Х6

250

0

0

0

0

0

0

9

9

0

0

0

0

0

1

Индексная строка

_

-14

-15

-7

-5

-15

-17

-9

-9

0

0

0

0

0

0

Страницы: 1 2 3 4 5

Еще о транспорте:

Определение проектных величин коэффициентов технической готовности и использования автомобилей
Коэффициент технической готовности Количество дней эксплуатации автомобиля за цикловой пробег Количество дней простоя автомобиля в ТО и ТР за цикл Дни простоя в КР DКР=dКР+dтранс Дни транспортировки автомобиля до авторемонтного завода. dтранс=(0,150,20) dКР dтранс=0,2dКР=0,2*25=5 dтранс=0,2 ...

Организация перевозок
Свидетельство о допуске АТС к перевозке опасных грузов (Приложение И) выдается ГИБДД Алтайского края после его технического осмотра. Тротил относится к первому классу – взрывчатые материалы, грузоотправитель (грузополучатель) должен получить разрешение на перевозку в ГИБДД УВД Алтайского края. Пере ...

Экономико-географическая характеристика региона – город Гомель
Гомель— город в Беларуси, административный центр Гомельской области и Гомельского района, второй по численности населения (484,3 тыс. человек на 1 января2010) город в стране. Расположен на юго-востоке республики на реке Сож в 302 км на юго-восток от Минска, Площадь города 121 км² (по состоянию ...

Главное Меню

Copyright © 2018 - All Rights Reserved - www.transportine.ru