Экономико-математическое моделирование затрат по перевозке товара

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСВТЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ УХТИНСКИЙ ГОСУДАРСВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

РЕФЕРАТ

По дисциплине: Математические модели информационных процессов управления

Выполнил:

Набока А.М.

Проверила:

Кудряшова О.М.

Ухта, 2012 год

Содержание

1. Постановка задачи

2. Выбор и обоснование метода решения задачи

3. Алгоритм решения методом «минимальной стоимости»

4. Решение задачи вручную

Список используемой литературы

Приложение

1. Постановка задачи

Три нефтеперерабатывающих завода с суточной производительностью 10, 8, 6 млн., галлонов бензина снабжают три бензохранилища, спрос которых составляет 6, 11 и 7 млн., галлонов. Бензин транспортируется в бензохранилища по трубопроводу. Стоимость перекачки бензина на 1 км., составляет 5 д. е., на 100 галлонов. Завод 1 не связан с хранилищем 3. Расстояние от заводов до бензохранилищ следующее:

Таблица:

Минимизируйте затраты.

2. Выбор и обоснование метода решения задачи

Транспортная модель используется для представления наиболее экономичного плана перевозки одного вида продукции из нескольких исходных пунктов в пункты назначения. Для построения транспортной модели используются следующие величины:

- Объем производства в каждом исходном пункте аi;

- Спрос в каждом пункте назначения bj;

- Стоимость перевозки единицы продукции из каждого исходного пункта в каждой пункт назначения cij.

Цель задачи состоит в определении количества продукции x_ij, которое следует перевезти из каждого исходного пункта в каждый пункт назначения, чтобы транспортные расходы были минимальными.

Транспортная задача называется сбалансированной или закрытой, если суммарный объем производства равен суммарному спросу:

Тогда в ограничениях знаки неравенства меняются на знаки равенства:

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

Транспортная модель может быть представлена с помощью транспортной таблицы, строки которой соответствуют исходным пунктам, столбцы - пунктам назначения, коэффициенты С_ij располагаются в правом верхнем углу каждой ячейки.

Пример: В исходных пунктах имеются запасы продукции 90, 400 и 110 тонн. Потребители должны получить продукт в количестве 140, 300, 160 тонн. Найти такое распределение груза, чтобы затраты на перевозку были минимальными, если матрица затрат имеет вид:

min Z = 2 х₁₁ + 5 х₁₂ + 2х₁₃ + 4х₂₁ + х₂₂ + 5х₂₃ + 3х₃₁ + 6х₃₂ + 8х₃₃

Далее схематично.

По формулам:

В данном случае задача сбалансирована, т. е., сумма объемов производства равна сумме спросов: 90 + 400 + 110 = 140 + 300 + 160 = 600. Если задача не сбалансирована, вводятся дополнительные фиктивные исходные пункты или пункты назначения, куда распределяется избыток или недостаток продукции. Т. к., пункт фиктивный, то стоимость перевозки берется, равной 0.

Специальные методы решения транспортной задачи повторяют шаги алгоритма:

- Нахождение начального допустимого решения или опорного плана;

- Проверка его на оптимальность;

- Нахождение нового решения, если решение не оптимально.

Нахождение начального допустимого решения можно осуществить тремя способами:

- Правило северо-западного угла;

- Метод минимальной стоимости;

- Приближенный метод Фогеля.

Метод северо-западного угла.

Приписывает переменной х₁₁ минимальное значение по объему производства и по спросу. Вычеркивается строка или столбец, где ограничение на спрос или на объем производства выполнено. Корректируется спрос или объем производства. Переходят к ближайшей не вычеркнутой ячейке таблицы. Процесс распределения завершается, когда остается не вычеркнутой одна строка или столбец.

Базисными переменными являются переменные, соответствующие заполненным клеткам таблицы, т. е., x₁₁, x₂₁, x₂₂, x₂₃, x₃₃.

Количество базисных переменных определяется по формуле:

m + n - 1

Где:

m и n - количество строк и столбцов соответственно.

Z = 90 * 2 + 50 * 4 + 300 + 50 * 5 + 110 * 8 = 1810 д. е.

Метод минимальной стоимости.

Из всей таблицы ищется ячейка, которой соответствует наименьшая стоимость, ей приписывается минимальное значение по объему производства и по спросу. Если таких переменных несколько, то выбирается любая. Вычеркивается строка или столбец, где ограничение выполнено, корректируются спросы и объемы производства. Далее среди не вычеркнутых ищется ячейка с минимальной стоимостью. Процесс завершается, когда остается не вычеркнутой одна строка или столбец.

1) х₂₂ = 300, так как С₂₂ = 1 - min, столбец 2 вычеркнут;

2) х₁₃ = 90, строка 1 вычеркнута;

3) х₃₁ = 110, строка 3 вычеркнута;

4) х₂₁ = 30, столбец 1 вычеркнут;

5) х₂₃ = 70, строка 2 вычеркнута.

Z = 90 * 2 + 30 * 4 + 300 + 70 * 5 + 110 * 3 = 1280 денежных единиц.

Приближенный метод Фогеля.

1. Вычислить штраф для каждой строки и столбца, вычитая наименьший элемент строки или столбца из следующего за ним элемента (по величине) той же строки или столбца;

2. В строке или столбце с самым большим штрафом выбрать переменную с самой низкой стоимостью и придать ей минимальное значение по спросу и объему производства. Скорректировать значение спроса и объема, вычеркнуть строку или столбец, где ограничение выполняется. Строка или столбец с нулевым значением производства или спроса в дальнейших вычислениях не участвует. Если остается не вычеркнутой строка или столбец с положительным объемом производства или спроса, найти базисную переменную с помощью метода наименьшей стоимости. Если всем не вычеркнутым строкам или столбцам соответствуют нулевые объемы производства и спроса, найти нулевые базисные переменные, используя метод минимальной стоимости;

3. Вычислить новые значения штрафов для не вычеркнутых строк и столбцов, перейти к пункту 2. Вычисления продолжаются, пока останется не вычеркнутой одна строка или столбец. Количество базисных переменных:

m + n - 1

Далее схематично.

По формуле:

m + n - 1 = 5

Z = 1280 денежных единиц. Из выше сказанного определили, что по условию нашей задачи самое правильно решение мы получим при решении методом минимальной стоимости.

3. Алгоритм решения методом «минимальной стоимости»

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

4. Решение задачи вручную

Для второго варианта:

Решение не оптимально, т. к.:

x₃₃ - включаемая в базис переменная;

х₃₂ - исключаемая из базиса переменная.

Или:

Z = 6 * 100 + 4 * 150 + 7 * 180 + 1 * 60 + 6 * 120 = 3240.

W = 50000 * (6 * 100 + 4 * 150 + 7 * 180 + 1 * 60 + 6 * 120) = 50000 * 3240 = 162000000 (д. е.) или 162 млн., д. е. - оптимальное решение методом минимальной стоимости.

Список используемой литературы

1. Кудряшова О.М. «Нахождение оптимального решения транспортной задачи методом минимальной.

2. Кудряшова О.М. Конспект лекций по дисциплине «Математические модели».

3. Кудряшова О.М. Конспект лекций по дисциплине «Алгоритмические языки».

Приложение

Выход формы решения на программном обеспечении, при запуске программы появляется окно, показанное на рисунке 1.Б.

математический экономический алгоритм

Для выхода из программы пользователь, должен нажать “Крестик”. После того, как пользователь вызвал форму для решения задачи минимальной стоимости, он должен ввести данные которые были предоставлены в условиях задачи. После нажать на кнопку «Решить» и появится форма с правильным решением как показано на рисунке 3.Б. Кнопка «Подставить значения» предназначена для автоматической подстановки значений для задачи 5 варианта.

Пользователь должен ввести «Количество поставщиков (заводы)» и «Количество потребителей (объекты)» которые были предоставлены ему в условиях задачи, нажать кнопку “Дальше” и появится форма для решения транспортной задачи методом минимальной стоимости.

Размещено на Allbest.ru