Новости  Акты  Бланки  Договор  Документы  Правила сайта  Контакты
 Топ 10 сегодня Топ 10 сегодня 
  
21.10.2015

Транспортная задача закрытая модель

Постановка и модели транспортной задачи линейного программирования……………………………………………………………… Постановка транспортной задачи и ее математическая модель……….. Закрытая модель транспортной задачи…………………………………….. Открытая модель транспортной задачи……………………………………. Методы нахождения опорных и оптимальных планов……………… Определение оптимального и опорного плана транспортной задачи…..

Каждый человек ежедневно, не всегда осознавая это, решает проблему: Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Соответствующий раздел математики называется математическим программированием. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.

Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности.

Реферат: Транспортная задача 5

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

Цель заданной работы - освоить математическую постановку транспортной задачи линейного программирования. Постановка и модели транспортной задачи линейного программирования. Постановка транспортной задачи и ее математическая модель. Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления или пунктов производства А i …, А m , в которых сосредоточены запасы однородных продуктов в количестве a 1 , Имеется n пунктов назначения или пунктов потребления В 1 , Известны также транспортные расходы С ij , связанные с перевозкой единицы продукта из пункта A i в пункт В j , i 1, …, m; j 1, Требуется составить такой план перевозок откуда, куда и сколько единиц продукта везти , чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок.

Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Пусть х ij - количество единиц продукта, поставляемого из пункта А i в пункт В j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:.

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

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

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

Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, то есть , 5. В ряде случаев не требуется, чтобы весь произведенный продукт в каждом пункте производства был реализован. В таких случаях баланс производства и потребления может быть нарушен:.

Введение этого условия приводит к открытой транспортной модели. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена. Действительно, подставляя значения в 2 и 3 , находим. Объединяя два последних неравенства в одно двойное, окончательно получаем.

Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. Для открытой модели может быть два случая:. Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений. Открытая модель решается приведением к закрытой модели. В случае б , когда суммарные потребности превышают. Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.

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

Методы нахождения опорных и оптимальных планов. Определение оптимального и опорного плана транспортной задачи. Как и при решении задачи линейного программирования, симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана. Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже. При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ.

Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом. Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы 2 и 3 и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы.

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

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

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

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

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

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

В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки. Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта: Четвертая перевозка осуществляется с пункта в пункт потребления , так как без учета первого, второго столбца и четвертой строки.

Пятая перевозка осуществляется с пункта в пункт потребления , так как без учета первого, второго столбца, третьей и четвертой строки. Шестая перевозка осуществляется с пункта в пункт потребления так как без учета первого, второго столбца, первой, третьей и четвертой строки.

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

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

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

Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:. Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками.

За конечное число итераций находится оптимальный план задачи. Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции из i-го пункта производства в j-ый центр потребления Cij приведена в таблице, где под строкой понимается пункт производства, а под столбцом -пункт потребления.

Кроме того, в таблицах в i-й строке указан объем производства в i-м пункте, а в j-м столбце указан спрос в j-м центре потребления. Составить план перевозок по доставке требуемой продукции в пункты потребления, минимизирующий суммарные транспортные расходы. Необходимые данные для решения задачи взять из представленной ниже таблицы. Это переменные задачи, значения которых должны быть определены в процессе решения.

Очевидно, что все переменные задачи не отрицательные, то есть X ij 0,. Обычно транспортная задача представляется в виде таблицы, где в ячейках помещаются переменные задачи X ij , а в правом верхнем углу ячейки стоят стоимости перевозки из пункта i в пункт j C ij.

В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи. Транспортная задача, для которой суммы чисел в последнем столбце и нижней строке равны, называется сбалансированной: Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец.

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

Вводим данные таблицы 1 и 2 в ячейки EXCEL. E7 введены стоимости перевозок табл. G8 находится объемы производства. А в ячейках B9: F12 находится объемы потребления. F15 — рабочие изменяемые ячейки, в которых будут вычисляться значения переменных задачи X ij. G15 нужно записать формулы для вычисления левых частей ограничений:. Формулы для вычисления левых частей ограничений введем в ячейки B Целевую функцию поместим в ячейку H Таким образом с предприятия А исходный пункт 1 следует 14 ед.

Все эти результаты видны в конечной таблице. При этом суммарная стоимость транспортных расходов составит ,8 рублей ячейка Н9. Найти опорный план транспортной задачи, в которой запасы на 3-х складах равны , , и 65 единиц, а потребности 4-х магазинов равны , 90, и единиц продукции.

Тарифы перевозки в рублях за единицу продукции следующие:. Решение методом северо-западного угла. О порный план имеет вид:. Решение методом минимального элемента. Найти опорный план транспортной задачи, в котором запасы на 3-х складах равны , и единиц продукции, а потребности 4-х магазинов равны , 50, и Таким образом, мы видим, что метод Фогеля дает наилучший результат, а метод северо-западного угла — наихудший.

В работе изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования.

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

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

К таким задачам относятся следующие:. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij.

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

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

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

Сборник задач и упражнений по математической статистике. Изд-во Института математики им. Соболева СО РАН, Математика для экономических специальностей. Основы математики и ее приложения в экономическом анализе: Решение задач линейного программирования. Главная Опубликовать работу О сайте. Математическая постановка транспортной задачи линейного программирования и решение её различным.

Сохрани ссылку на реферат в одной из сетей: Махачкала Содержание Введение……………………………………………………………………………………. Методы нахождения опорных и оптимальных планов………………12 2. Метод северо-западного угла……………………………………………………14 2. Метод аппроксимации Фогеля…………………………………………………19 2. Постановка транспортной задачи и ее математическая модель Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом.

Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой: Формально это означает, что , i 1, …, m 2 Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности.

Это условие полного удовлетворения спроса: Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, то есть , 5 то модель такой транспортной задачи называется закрытой. В таких случаях баланс производства и потребления может быть нарушен: Закрытая модель транспортной задачи Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена.

Открытая модель транспортной задачи Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. Для открытой модели может быть два случая: Определение оптимального и опорного плана транспортной задачи Как и при решении задачи линейного программирования, симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана. Опорный план имеет вид; 20 0 0 0 0 80 70 0 0 0 0 50 2.

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

Пример Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи: Рассмотрим задачу, приведенную для методов северо-западного угла и минимального элемента Решение: Метод потенциалов Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче.

Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj: Таблица1 Предприятия Стоимость перевозки единицы продукции Объем произ-водства Пункты потребления 1 2 3 4 А 7,3 9 3 10 14 В 3 10 3 9 30 С 7 11 3 2 20 D 8 5 9 2 32 E 4,8 9 10 5 16 Объемы потребления 60 10 20 10 I. Таблица в этом случае имеет вид: Транспортные расходы на перевозку по доставке требуемой продукции вычисляются по формуле: G15 нужно записать формулы для вычисления левых частей ограничений: F11; в G12 должна быть сумма ячеек B F12; в G13 должна быть сумма ячеек B F13; в G14 должна быть сумма ячеек B F14; в G15 должна быть сумма ячеек B C15; в D16 должна быть сумма ячеек D D15; в E16 должна быть сумма ячеек E E15; в F16 должна быть сумма ячеек F F15; Целевую функцию поместим в ячейку H9: Таблица исходных данных имеет вид: Тарифы перевозки в рублях за единицу продукции следующие: Заключение В работе изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования.

К таким задачам относятся следующие: Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком; - оптимальные назначения, или проблема выбора. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности; - задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции; - увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега.

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

Высшая школа, 6. Стоимость перевозки единицы продукции.

  Комментарии к новости 
 Главная новость дня Главная новость дня 
М семеновская на карте
Сахар норма у мужчин
Вязать сапоги крючком видео
Вечернее правило оптина пустынь слушать
Каким курсом пить
Рецепт мацы в домашних условиях
Понятие и значение соучастия в уголовном праве
Пени за коммунальные услуги за год
Примерной инструкции по делопроизводству
 
 Эксклюзив Эксклюзив 
Новости пулково видео сегодня
Где принимают цветной металл улан удэ
2017 для брака
Как сделать объемный хвост на средние волосы
Как выбрать смартфон недорогой но хороший 2017
Дед мороз крючком описание