Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    Сам записывает клиентов и напоминает им о визите;
    Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом
  • Математическая модель транспортной задачи

    Лабораторная работа №3

    Транспортные задачи и логистика, задачи о назначениях и отборе

    В деловой практике широко используются две модели: транспортная задача и задача о назначениях. Представление о том, что такое транспортная задача, у специалиста по исследованию операций и у менеджера отдела логистики очень сильно различаются. Сточки зрения менеджера, транспортные задачи – это любые задачи, связанные с оптимизацией перевозок. С точки зрения специалиста по исследованию операций, транспортная задача– это специальный вид задачи линейной оптимизации, для которой из-за её формулировки и специфических ограничений существуют свои эффективные алгоритмы решения. Это могут быть задачи, не связанные с перевозками.

    Математическая модель транспортной задачи

    Транспортная задача. Классическая транспортная задача (ТЗ) имеет своей целью минимизацию транспортных издержек (или максимизацию прибыли) при перевозках однотипных грузов (контейнеров, вагонов, машин и т.п.) от нескольких поставщиков (с различных складов), расположенных в разных местах, к нескольким потребителям. При этом принимается в расчёт только переменные транспортные издержки, которые пропорциональны количеству перевезённых единиц груза. Рассмотрим задачу.

    Задача №2.1.

    В районе имеется два песчаных карьера, с которых песок вывозится на 5-ти тонных грузовиках. Предприятия, S1и S2, разрабатывающие карьеры (поставщики песка), могут поставлять соответственно 100 и 200 грузовиков с песком в день. В этом районе имеется три завода железобетонных конструкций (потребители песка) D1, D2 и D3, которым требуется соответственно 80, 90 и 130 грузовиков с песком в день. Стоимости перевозки песка одним грузовиком от карьера Si(i=1, 2) к заводу Dj(j=1, 2, 3) в условных единицах, приведены в таблице 2.1.

    Таблица 2.1. Параметры задачи №2.1

    Математическая модель задачи №2.1. В нашей задаче шесть маршрутов.

    Обозначим количество грузовиков Xij, перевозимое с карьера Siна завод Dj.

    Таким образом, у нас шесть переменных. Целевая функция в данной задаче -суммарные транспортные издержки – равна сумме произведений переменных решения Xijна стоимости перевозки единицы груза Cij, приведённые в табл. 2.1.

    Таким образом,

    Чтобы удовлетворить все требования потребителей, т.е. выполнить все заказы, надо чтобы:

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

    Так как поставки не могут быть отрицательными, то Xij≥ 0.

    При этом предполагается, что спрос и предложение отвечают условию баланса, т.е.S1+S2=D1+D2+D3.

    В общем случае ТЗ выглядит так: Пусть имеется «m» поставщиков некоторойоднородной продукции и «n» потребителей этой продукции. В «m» пунктахотправления А1, А2, …, Аm сосредоточено определённое количество некоторогооднородного груза, (i=1, 2, …, m). Данный груз потребляется в «n» пунктах B1, B2, …, Bn. Объёмы потребления bj (j=1, 2, …n). Известны расходы на перевозку единицы груза из пункта Ai в пункт Bj, которые равны cij.

    МатрицаС = (сi, j), i = 1, …, m; j = 1, …, n. называется тарифной матрицей.

    где cij – стоимость перевозки единицы груза от i-го поставщика к j-му потребителю.

    Эта матрица имеет «m» строк (число поставщиков) и «n» столбцов (число потребителей). Требуется составить такой план прикрепления потребителей к поставщикам (план перевозок), при котором весь груз от поставщиков будет вывезен, потребности потребителей полностью удовлетворены и общая величина транспортных издержек будет минимальной.

    Пусть Xij – количество груза, перевозимого из пункта Ai в Bj, тогда целевая функция имеет вид:

    при ограничениях: . (20)

    Условия (20) означают полное удовлетворение спроса во всех пунктах потребления и полный вывоз продукции от всех поставщиков. Условие баланса для ТЗ имеет вид:

    .

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

     

    Алгоритм решение транспортной задачи с помощью MS–Excel

     

    Для практического решения ТЗ с помощью MS-Excel рассмотрим более сложный пример, на тему «рациональных перевозок грузов».

    Задача №2.2. Пусть имеется 4 поставщика и 5 потребителей. Издержки перевозки единицы груза от i-го поставщика в j-й пункт назначения, запасы поставщиков и заказы потребителей даны в таблице 2.4. Оптимизировать план перевозок.

    Таблица 2.4. Параметры задачи №2.2

    Организуем данные так, как показано в таблице 2.5.

    Таблица 2.5. Организация данных задачи №2.2 на листе MS-Excel

    1. В ячейках I4-I7 стоят суммы произведений цены единицы груза на объём перевозок от i-го поставщика к любому потребителю.

    В ячейке I8 сумма этих сумм (т.е. двойная сумма), это и есть целевая функция, минимум которой надо найти.

    В ячейки I10: I13 внесены ограничения на количества груза, вывезенного от каждого поставщика, т.е. запасы.

    В ячейки B14: F14 внесены ограничения на количества груза, необходимого потребителям, т.е. заказы.

    2. Далее вызываем «Поиск решения».

    а) Целевая ячейка: I8, - Мин;

    б) Изменяя ячейки: B11: F14;

    с) Ограничения: B11: F14≥ 0 (перевозки не могут быть отрицательными), I10: I13=0 (ограничения на количества груза от каждого поставщика), B14: F14=0 (ограничения на количества груза каждому потребителю). При такой организации данных все перевозки окажутся целыми числами, если целыми являются числа в колонках «Запасы» и строке «Заказы».

    3. Надо проверить, чтобы в полученном решении было ровно m+n-1 ненулевых перевозок.

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

    Ответ: Fmin=980 (усл.ден.ед) при плане .

    Итоговое распределение перевозок, а также значения «теневых цен», соответствующие пустым клеткам, можно использовать при проведении анализа модели на чувствительность.

     

    <== предыдущая лекция | следующая лекция ==>
     | Одномерный массив.




    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.