Транспортная задача
Экономико-математическая модель транспортной задачи составления плана перевозок, позволяющего вывести все грузы, полностью удовлетворить потребности и имеющей минимальную стоимость. Решение транспортной задачи с помощью средства Excel "Поиск решения".
| Рубрика | Экономико-математическое моделирование |
| Вид | задача |
| Язык | русский |
| Дата добавления | 27.11.2019 |
| Размер файла | 175,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru//
Транспортная задача
Транспортная задача является одной из наиболее распространённых задач линейного программирования и находит широкое практическое приложение.
Постановка транспортной задачи. Некоторый однородный продукт, сосредоточенный у k поставщиков Аi в количестве аi (i = 1,…,k) единиц, необходимо доставить n потребителям Bj в количестве bj (j=1, …, n) ед. Известна стоимость сij перевозки единицы груза от i-го поставщика к j-му потребителю.
Необходимо составить план перевозок, позволяющий вывести все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.
Сформулируем экономико-математическую модель транспортной задачи. Обозначим через xij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от i-го поставщика к j-му потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки составит сij xij .
Стоимость всего плана выразится двойной суммой
Систему ограничений получаем из следующих условий задачи:
а) все грузы должны быть перевезены, т.е.
,
б) все потребности должны быть удовлетворены, т.е.
Таким образом, математическая модель транспортной задачи имеет следующий вид: найти минимальное значение линейной функции
при ограничениях
(*)
В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.
Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие (2.4.5), называется закрытой моделью; в противном случае - открытой. Для открытой модели может быть два случая:
а) суммарные запасы превышают суммарные потребности
б) суммарные потребности превышают суммарные запасы
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Найти минимальное значение линейной функции
при ограничениях
(случай а)
(случай б)
Открытая модель решается приведением к закрытой модели.
В случай а , когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребность которого
В случае б , когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Ak+1, запасы которого
Как стоимость перевозки единицы груза до фиктивного потребителя, так и стоимость перевозки груза от фиктивного поставщика полагаются равными нулю, так кА груз в обоих случаях не перевозится.
Транспортная задача имеет n+k уравнений с k•n неизвестными.
Матрицу Х=(xij)k,n, удовлетворяющую условиям (*) называют планом перевозок транспортной задачи (xij - перевозками).
План Х* , при котором целевая функция обращается в минимум, называется оптимальным.
Решение транспортной задачи с помощью средства Excel «Поиск решения»
транспортная задача перевозка
Исходные данные транспортной задачи приведены схематически: внутри прямоугольника заданы удельные транспортные затраты на перевозку единицы груза (cij), слева указаны мощности поставщиков (ai), а сверху - мощности потребителей (bj). Найти оптимальный план закрепления поставщиков за потребителями (xij).
|
Мощности поставщиков |
Мощности потребителей |
||||
|
250 |
100 |
150 |
50 |
||
|
80 |
6 |
6 |
1 |
4 |
|
|
320 |
8 |
30 |
6 |
5 |
|
|
100 |
5 |
4 |
3 |
30 |
|
|
50 |
9 |
9 |
9 |
9 |
В данной задаче суммарные запасы равны суммарным потребностям, т.е.
Таким образом, транспортная задача является закрытой.
Ввод условий задачи состоит из следующих основных шагов:
Создание формы для ввода условий задачи.
Ввод исходных данных.
Ввод зависимостей из математической модели.
Назначение целевой функции.
Ввод ограничений и граничных условий.
Изменяемые ячейки В3:Е6. В эти ячейки будет записан оптимальный план перевозок - xij.
Ввести исходные данные задачи (рис.8).
В ячейку А3 ввести формулу =СУММ(В3:Е3). Скопировать её в ячейки А4, А5, А6.
В ячейку В7 ввести формулу =СУММ(В3:В6). Скопировать её в ячейки С7, D7, E7.
Выражение для вычисления значения целевой функции в ячейке В15 получено с помощью функции СУММПРОИЗВ(В3:Е6; В10:Е13).
После вызова Поиска решения курсор подвести в поле «Установить целевую ячейку» и ввести адрес: В15. Ввести направление целевой функции «минимальному значению». Поместить курсор в поле «Изменяя ячейки». Ввести адреса изменяемых ячеек В3:Е6. Далее следует добавить ограничения.
Рис. 8. Создание формы для ввода условий задачи.
Рис. 9. Введены зависимости из математической модели.
Все грузы должны быть перевезены, т.е.
Все потребности должны быть удовлетворены, т.е.
После ввода последнего ограничения вместо добавить вести ОК. на экране появится окно Поиск решения с введёнными ограничениями (см. рис. 9).
Решение задачи
Решение задачи производится сразу же после ввода данных, когда на экране находится окно Поиск решения. С помощью окна Параметры можно вводить условия для решения оптимизационных задач. В нашей задаче следует установить флажок «неотрицательные значения» и флажок «линейная модель» (рис. 10). Нажать Ок, затем Выполнить.
Рис. 10. Установка параметров.
На экране появится диалоговое окно Результаты поиска решения и само решение. (рис.11)
Рис. 11. оптимальный план перевозок.
В результате решения получен оптимальный план перевозок:
|
Матрица перевозок (изменяемые ячейки) |
|||||
|
80 320 100 50 |
0 200 0 50 |
0 0 100 2.13Е-14 |
80 70 0 0 |
0 50 0 0 |
|
|
550 |
250 |
100 |
150 |
50 |
Х13 = 80 ед. груза следует перевезти от 1-го поставщика 3-му потребителю;
Х21 = 200 ед. груза следует перевезти от 2-го поставщика 1-му потребителю;
Х23 = 80 ед. груза следует перевезти от 2-го поставщика 3-му потребителю;
Х24 = 50 ед. груза следует перевезти от 2-го поставщика 4-му потребителю;
Х32 = 100 ед. груза следует перевезти от 3-го поставщика 2-му потребителю;
Х41 = 50 ед. груза следует перевезти от 4-го поставщика 1-му потребителю;
Х42 = 0 ед. груза следует перевезти от 4-го поставщика 2-му потребителю.
Общая стоимость перевозок равна 3200.
Размещено на Allbest.ru
...Подобные документы
Основные подходы и способы решения транспортной задачи, ее постановка и методы нахождения первоначального опорного решения. Математическая модель транспортной задачи и алгоритм ее решения методом потенциалов. Составление опорного плана перевозок.
курсовая работа [251,0 K], добавлен 03.07.2012Экономико-математическая модель прикрепления пунктов отправления к пунктам назначения, расчет оптимального плана перевозок. Решение транспортной задачи метолом потенциалов (перераспределение ресурсов по контуру), пример вычислительного алгоритма.
учебное пособие [316,8 K], добавлен 17.10.2010Типы транспортных задач и методы их решения. Поиск оптимального плана перевозок методом потенциалов. Решение задачи с использованием средств MS Excel. Распределительный метод поиска оптимального плана перевозок. Математическая модель, описание программы.
курсовая работа [808,7 K], добавлен 27.01.2011Математическая постановка задачи и выбор алгоритма решения транспортной задачи. Проверка задачи на сбалансированность, её опорное решение и метод северо-западного угла. Транспортная задача по критерию времени, поиск и улучшение решения разгрузки.
курсовая работа [64,7 K], добавлен 14.10.2011Транспортная задача линейного программирования, закрытая модель. Создание матрицы перевозок. Вычисление значения целевой функции. Ввод зависимостей из математической модели. Установление параметров задачи. Отчет по результатам транспортной задачи.
контрольная работа [202,1 K], добавлен 17.02.2010Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
реферат [4,1 M], добавлен 09.03.2011Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Экономико-математическая модель оптимального плана выпуска продукции. Оптимальная организация рекламной компании. Решение транспортной задачи: нахождение суммарных затрат на перевозку. Задача об оптимальном назначении (линейного программирования).
контрольная работа [812,0 K], добавлен 29.09.2010Численные коэффициенты функции регрессии. Построение транспортной модели. Нахождение опорного плана методом Фогеля. Построение модели экономичных перевозок. Составление транспортной матрицы. Общая распределительная задача линейного программирования.
курсовая работа [1,3 M], добавлен 11.06.2010Математическая постановка и алгоритм решения транспортной задачи. Сбалансированность и опорное решение задачи. Методы потенциалов и северо-западного угла. Блок-схема. Формы входной и выходной информации. Инструкция для пользователя и программиста.
курсовая работа [113,8 K], добавлен 10.11.2008Решение графическим методом задачи линейного программирования с двумя неизвестными. Решение транспортной задачи методом северо-западного угла и методом минимальной стоимости. Системы массового обслуживания. Стохастическая модель управления запасами.
контрольная работа [458,1 K], добавлен 16.03.2012Пример постановки транспортной задачи и особенности экономико-математической модели. Оптимальный способ организации снабжения потребителей продукцией предприятий-изготовителей. Параметры перевозок. Математический анализ модели, выбор метода решения.
курсовая работа [2,0 M], добавлен 04.01.2016Основные методы решения задачи оптимального закрепления операций за станками. Разработка экономико-математической модели задачи. Интерпретация результатов и выработка управленческого решения. Решение задачи "вручную", используя транспортную модель.
курсовая работа [1,0 M], добавлен 25.01.2013Содержание методов аппроксимации Фогеля, потенциала, наименьшей стоимости и северо-западного угла как путей составления опорного плана транспортной задачи на распределение ресурсов с минимальными затратами. Ее решение при помощи электронных таблиц.
курсовая работа [525,7 K], добавлен 23.11.2010Построение экономико-математической модели. Решение задачи с помощью надстройки MS Excel "Поиск решения". Целевая функция задачи. Формульный вид таблицы с исходными данными. Результат применения надстройки. Организация полива различных участков сада.
контрольная работа [1,3 M], добавлен 28.11.2012Разработка экономико-математической модели и решение задачи линейного программирования с использованием математических методов. Транспортная задача в матричной постановке и ее свойства. Построение исходного допустимого плана. Критерий оптимальности.
курсовая работа [111,1 K], добавлен 16.01.2011Особенности формирования и способы решения оптимизационной задачи. Сущность экономико-математической модели транспортной задачи. Характеристика и методика расчета балансовых и игровых экономико-математических моделей. Свойства и признаки сетевых моделей.
практическая работа [322,7 K], добавлен 21.01.2010Транспортная задача (Т-задача) как одна из наиболее распространенных специальных задач линейного программирования. Порядок и закономерности постановки данной задачи, аналитический и графический методы. Открытые и закрытые транспортные модели, их решение.
контрольная работа [419,4 K], добавлен 06.08.2010Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.
контрольная работа [158,7 K], добавлен 15.10.2010Экономико-математическая модель транспортной задачи. Определение оптимального плана перевозок. Точечный и интервальный прогнозы трудоемкости производства. Матрица коэффициентов полных и прямых затрат. Среднее квадратическое отклонение от линии тренда.
контрольная работа [123,9 K], добавлен 30.04.2009
