новая папка 1 / 233236

Так как в табл. 11 имеются полюса, снова рассчитываем d- и h-параметры. Получено:

d12 = 2 + 0 = 2, d24 = 3 + 2 = 5, d42 = 3 + 0 = 3.

Анализируя полученные значения, выбран h(i0,j0) = d24 = 5.

Организуем перевозку из пункта 2 в пункт 4 (рис. 1, в). Вычеркивается строка i0 = 2 и столбец j0 = 4. Чтобы избежать зацикливания, с42=\\\\. Получена матрица табл. 12.

Получена тривиальная матрица (2х2). По значениям этой матрицы построены две связи: 1 – 2 (так как по табл. 12 «расстояние» между этими пунктами самое короткое) и 4 – 3, чтобы получить замкнутый циклический маршрут (рис. 1, г и 1, д соответственно).

Протяженность кольцевого маршрута составляет 28 км. L = 6 + 4 + 3 + 5 + 10 = 28 (км).

д

Рис. 1. Результаты конструирования маршрута (по шагам).

3. Решение линейной задачи симплексным методом

АТП имеет возможность перевезти на выбор три вида грузов: песок,

щебень и глину. Нужно перевезти грузы в таком объеме и столько, чтобы

За перевозку 1 т первого груза плата составит 600 рублей, 1 т второго груза - 500 рублей и 1 т третьего груза - 450 рублей.

Бригада автомобилей за смену может перевезти не больше 200 т, если она с грузом Х1 сделает 6 рейсов, с грузом Х2 - 3 рейса, с грузом Х3 - 5 рейсов; не более 300 т, если она с грузом Х1 сделает 10 рейсов, с грузом Х2 - 8 рейсов, с грузом Х3 - 4 рейса; не более 230 т, если она с грузом Х1 сделает 4 рейса, с

4Х1 + 4Х2 + 8Х3 + 0 Х4 + 0 X5 + 1 Х6 = 230.

С учетом добавочных переменных условие (4) будет выглядеть так:

С1 Х1 + С2:Х2 + С3Х3 + С4Х4 + С5Х5 + С6Х6 →mах,

где С1 =600, С2 = 500, С3 = 450, С4 = 0, С5 = 0, С6 =0.

Для решения подобных задач используется симплекс-метод. Система ограничений записывается так:

а11X1 + а12 Х2 +...+а1nХn≤ b1 а21X1 + а22 Х2 +...+а2nХn≤ b2

……………………………

аm1X1 + аm2 Х2 +...+аmnХn≤ bm.

Функционал F = С1 Х1 + С2:Х2 + … + СnХn → mах, где Сi – число рейсов.

Составим симплексную таблицу, структура которой выглядит так, как показано в табл. 13.

В столбце «Базис» записывают обозначения столбцов, образующих единичную матрицу. В нашем примере исходная единичная матрица состоит из коэффициентов при неизвестных (Х4, Х5, Х6), а столбец Х0 – состоит из свободных членов.

Воспользуемся системой уравнений (4) и заполним симплекс-таблицу. В

верхней строчке корпуса таблицы расписаны коэффициенты при переменных и свободном члене верхнего уравнения, остальное – очевидно.

Таблица 14

Начальная симплекс-таблица

Итоговая строка заполнена так: величина Х в базисе умножена на число, обозначенное в первой колонке (число Сi). Затем все числа данного столбца суммируются, из суммы вычитается число, обозначенное в целевой строке.

Итоговая строка получена так: из первого столбца 200·0+300·0 + 230·0=0 минус 0 из целевой строки. Во втором столбце 6·0+10·0+4·0=0, минус 600

равно - 600. Далее идет - 500, - 450, 0, 0, 0.

Правила выполнения задачи максимизации при симплекс-методе решения оптимизационных задач: 1) если все элементы итоговой строки неотрицательны, план задачи приведен к оптимальному; 2) в итоговой строке симплекс-таблицы содержится отрицательный элемент, а в этом же столбце Xj нет ни одного положительного числа, оптимального плана не существует; 3) в столбце Xj есть хотя бы один положительный элемент, а наименьшее из отношений свободных членов (Х0) к положительным элементам столбца Xj

положительно, возможен переход к лучшему базисному плану.

Начальный базисный план не оптимизирован, но существуют перспективы перехода к лучшему базисному плану, поскольку все отношения свободных членов X0 к любому члену колонок Х1, X2, Х3 явно больше нуля.

Для улучшения плана в табл. 14 введены ключевой столбец и ключевая строка (столбец X1, строка X5). Число, находящееся на пересечении ключевой строки и ключевого столбца, назовем ключевым, оно равно 10.

Делим каждую цифру ключевой строки на ключевой элемент. Получена ситуация, обозначенная в табл. 15.

Таблица 15

Промежуточная таблица при оптимизации симплекс-плана

В ключевой строке табл. 15 все элементы делятся на ключевой элемент, в данном случае 10. Остальные строки табл. 16 получены следующим образом:

Есть возможность улучшения плана, поскольку во всех столбцах основания таблицы присутствуют положительные элементы. Рассчитаем итоговую строку (см. табл. 15):

-третий столбец (Х0): 20·0 + 30·600 + 110·0 - 0 = 18 000,

-четвертый столбец (X1): 0·0 + 1·600 - 0·0 - 600 = 0,

-пятый столбец (Х2): 1,2·0 + 0,8·600 + 0,8·0 - 500 = -20,

-шестой столбец (Х3): 2,6·0 + 0,4·600 + 6,4·0 - 450 = -210,

-седьмой столбец (Х4): 1·0 + 0·600 + 0·0 - 0 = 0,

-восьмой столбец (Х5): 0,6·0 + 0,1·600 - 0,4·0 - 0 = 60,

-девятый столбец (Х6): 0·0 + 0 ·600 + 1·0 - 0 = 0.

После первого шага получить оптимальный план не удалось, поскольку в итоговой строке присутствуют отрицательные величины.

В качестве ключевой выбраны строка Х4 и столбец Х3, поскольку в итоговой строке он имеет отрицательную величину. Используя тот же алгоритм, получен результат, показанный в табл. 16.

Таблица 16

Оптимальное решение

Как можно судить по итоговой строке табл. 16, получено оптимальное решение. Необходимо перевезти 7,69 т третьего груза, 30 т первого груза, вторым грузом придется пренебречь. Он снижает эффективность работы перевозчика. За выполненную работу будет получена сумма 21 460 рублей.

Библиографические ссылки

1.Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. – М.: Финансы и статистика, 2006. – 432 с.

2.Витвицкий Е.Е., Николин В.И., Мочалин С.М. Грузовые автомобильные перевозки. – Омск: Вариант-Сибирь. – 2004.- 480 с.

Содержание

1.Оптимизация маятниковых маршрутов ………………………….…………3

2.Оптимальное построение кольцевых маршрутов……………..……………5

3.Решение линейной задачи симплексным методом……………………..…10

Организация перевозочных услуг и безопасность транспортного процесса

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению практических работ

Составители: Корчагин Виктор Алексеевич Ризаева Юлия Николаевна

Ризография. Печ. л. 1,0. Тираж 100 экз. Заказ № . Издательство Липецкого государственного технического университета.

Полиграфическое подразделение Издательства ЛГТУ. 398600 Липецк, ул. Московская, 30.