Оптимизация перевозок

Оптимизация перевозок

Рис.

отчет устойчивость перевозка

На заказ строительной компании песок перевозиться от трех поставщиков (карьеров) пятим потребителям (строительным площадкам). Стоимость на доставку включает себестоимость объекта, потому строительная компания заинтересована обеспечить потребности своих стройплощадок в песке самым дешевым способом. Дано: запасы (предложения) песка на карьерах (поставщиков); потребности (спрос) песка стройплощадок (потребителей); затраты (цена) на транспортирования между каждой парой «поставщик-потребитель». Нужно найти схему оптимальных перевозок для удовлетворения нужд (откуда и куда), при котором общие затраты были бы минимальными.

Экономико-математическая модель.

Найти План перевозок при котором:

1.       Об_затраты=План*Цена_перевозок - min

2.       При ограничениях: Ввезено=Потребности; Вывезено<=Запасы и План>=0

Реализация симплекс метода

Целевая функция:

(x_ij, i=, j=) → min ), где:

_ij - количество груза из i- карьера на j-стройплощадку

C_ij - стоимость доставки 1 груза из i-карьера на j-стройплощадку

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

Так как среди исходного набора условий были равенства, мы ввели искусственные переменные.

Определяем базисные и свободные переменные.

Составляем условие для вспомогательного решения.

Мы видим, что в строке имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим максимальный по модулю отрицательный элемент, который будем вводить в базис. Так как коэффициенты у нас отсутствуют, то будем выбирать его произвольно. Вводим x₁₂.

Мы видим, что в строке имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим максимальный по модулю отрицательный элемент, который будем вводить в базис. Так как коэффициенты у нас отсутствуют, то будем выбирать его произвольно. Вводим x₁₃.

Мы видим, что в строке имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим максимальный по модулю отрицательный элемент, который будем вводить в базис. Так как коэффициенты у нас отсутствуют, то будем выбирать его произвольно. Вводим x₁₄.

Мы видим, что в строке имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим максимальный по модулю отрицательный элемент, который будем вводить в базис. Так как коэффициенты у нас отсутствуют, то будем выбирать его произвольно. Вводим x₁₅.

Найденное решение оптимально для вспомогательного решения.

Выражаем базисные переменные через свободные.

Мы видим, что в строке имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим максимальный по модулю отрицательный элемент, который будем вводить в базис. Вводим x₂₂.

Выражаем базисные переменные через свободные.

Выражаем базисные переменные через свободные.

Мы видим, что в строке имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим максимальный по модулю отрицательный элемент, который будем вводить в базис. Вводим x₃₄.

= x₃₁= x₃₂= x₃₃= x₃₅=x₃₆=0 -свободные

Выражаем базисные переменные через свободные.

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение. Так как исходной задачей был поиск минимума, оптимальное решение есть свободный член строки F, взятый с противоположным знаком. Найдено оптимальное решение F=1149 при значениях переменных равных: x₁=42, x₂₂=20, x₁₃=20, x₁₄=23, x₁₅=60, x₂₃=80, x₃₄=52.

Решение задачи в среде Excel

Создадим таблицу с формулами, которые связывают план, ограничения и целевую функцию (Об_затраты):

Рис.

·              столбец Вывезено заполняем формулой: =СУММ (План_карьеры);

·              строку Ввезено заполняем формулой: =СУММ (План_стр_пл);

·              в столбец Остаток вводим формулу: Запас-Вывезено;

·              в целевую ячейку (Об_затраты) вводим формулу: =СУММПРОИЗВ (Цена; План).

Рис.

Запускаем программу Поиск решений командой Данные/Анализ/Поиск решения (В Excel 2007) Сервис/Поиск решения (В Excel 2003 и ниже). В полях Установить целевую ячейку, Изменяя ячейки, Ограничения вводим соответствующие адреса ячеек. Так как это линейная модель, то не забываем фиксировать в окне Параметры поиска решений переключатель на позицию Линейная модель и Неотрицательные значения. Нажимаем кнопку Выполнить и в появившемся окне Результаты поиска решения выводим отчёт об устойчивости.

Рис.

Анализ результатов

Минимальные затраты на транспортирование составляют 1149 д. ед. Нормированная стоимость показывает, до какого значения нужно уменьшить затраты на перевозку, что бы невыгодные маршруты стали выгодными. Теневые цены запасов поставщиков есть отрицательные числа, они показывают, как уменьшиться Об_затраты при увеличении дефицитных запасов поставщиков. Теневые цены потребностей потребителей указывают, как увеличится Об_затраты при увеличении потребностей.

Отчёт об устойчивости

Рис.

Выводы

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

Окончательное значение 1 - оптимальный план задачи. В нашем случае, чтобы получить минимальные затраты на транспортировку в размере 1149 д. ед.

Приведенная стоимость - Этот показатель, как изменится оптимальное значение ЦФ при перевозе товаров, цен на которые нет в оптимальном плане.

Целевая функция коэффициент - коэффициенты ЦФ;

Допустимое увеличение 1 и допустимое уменьшение 1 - границы изменений значений коэффициентов ЦФ при условии, что количество оптимальной продукции (план) не изменится.

Окончательное значение 2 - количество использованных ресурсов и спрос;

Теневая цена - касается ограничений, то есть, определенное значение указывает на «ценность» ограниченного ресурса в сравнении с другими ресурсами. Этот показатель указывает как изменится оптимальное значение ЦФ (Доход) при изменении запасов ресурсов на 1 единицу.

Ограничение правая сторона - запасы ресурсов;

Допустимое увеличение 2 и допустимое уменьшение 2 - задают диапазон для ограничение правая сторона, в котором действует теневая цена (аналогично 4, 5).