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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


реферат Транспортная задача с открытой моделью. Способ решения

Информация:

Тип работы: реферат. Добавлен: 18.05.2012. Сдан: 2011. Страниц: 6. Уникальность по antiplagiat.ru: < 30%

Описание (план):


 
   Федеральное агентство по образованию
    Государственное образовательное учреждение высшего  профессионального образования
   государственный социально-экономический университет 
 
 
 
 

   Реферат
   на  тему
   «Транспортная задача с открытой моделью. Способ решения » 
 
 
 
 
 
 
 
 
 
 
 
 

-  2010
Содержание
Введение             3
    Транспортная задача:  общая постановка, цели, задачи     4
    Транспортная задача с открытой моделью       7
    Решение транспортной задачи с открытой моделью на примере метода минимального элемента          15
Заключение            18
Список  использованных источников        20
Приложения             21
Приложение А            21
Приложение Б            22 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение
     Я выбрала эту тему реферата, потому что каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах («линейное программирование, динамическое программирование» и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование». С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу1. Актуальность выбранной тематики реферата заключается в том, что к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.
     Новизна и практическая значимость работы обусловлена  тем фактом, что транспортная задача линейного программирования получила в настоящее время широкое  распространение в теоретических  обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта. 

    Транспортная задача: общая постановка, цели, задачи
           Под названием «транспортная  задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам  линейного программирования и могут  быть решены симплексным методом2. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение3.
     Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аi …, Аm, в которых сосредоточены запасы однородных продуктов в количестве a1, ..., аm единиц. Имеется n пунктов назначения (или пунктов потребления) В1, ..., Вm, потребность которых в указанных продуктах составляет b1, ..., bn единиц. Известны также транспортные расходы Сij, связанные с перевозкой единицы продукта из пункта Ai в пункт Вj, i 1, …, m; j 1, ..., n. Предположим, что 

      ,  

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

       

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

      , i 1, …, m  

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

      , j 1, …, n  

     Объемы  перевозок - неотрицательные числа, так как перевозки из пунктов  потребления в пункты производства исключены:
     xij 0, i 1, ..., m; j 1, ..., n 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

    , j 1, …, n и  , i 1, …, m,  

определяемое  матрицей X=(xij)(i 1, …, m; j 1, ..., n), называется планом транспортной задачи.
    Определение 2.
План X*=(x*ij)(i 1, …, m; j 1, ..., n), при котором функция  

     

принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
     В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с баз потребителям .
     Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени) 6.
      Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно ,а общее количество имеющегося в наличии груза– : 

    ; 

заказы  каждого из потребителей (потребности) обозначим соответственно , а общее количество потребностей – : 

    , 

Тогда при условии
     

– открытую модель транспортной задачи.
в случае же открытой модели либо все заказчики  удовлетворены и при этом на некоторых  базах остаются излишки груза  , либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены .
     Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
     План  перевозок с указанием запасов  и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок (приложение А)
     Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю : совокупность этих величин образует матрицу (матрицу перевозок).
    Очевидно, переменные должны удовлетворять условиям: 


     

     Система содержит уравнений с неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях7.
     Такая структура системы позволяет  легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием , .Перепишем систему в виде 

     

где символы  и означают суммирование по соответствующему индексу. Так, например, 

     

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

     

    или короче 

     

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

     

     Так как для закрытой модели транспортной задачи , то полученные нами уравнения одинаковы и, исключив из одного из них неизвестное , мы получим уравнение-тождество 0=0, которое из системы вычеркивается.
     Итак, преобразование системы свелось  к замене двух уравнений (первого  горизонтального и первого вертикального) уравнение. Остальные уравнения  остаются неизменными. Система приняла вид
     

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

     Требуется в области допустимых решений  системы уравнений и найти  решение, минимизирующее линейную функцию.
     Замечание 1. Не исключаются здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей свободных неизвестных вписываются в соответствующую клетку, и эта клетка считается заполненной.
     Замечание 2. Под величинами , очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, выражены в тоннах, а в километрах, то величина , определяемая формулой, является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.
     Таким образом, мы видим, что транспортная задача является задачей линейного  программирования. Для ее решения  применяют также симплекс-метод, но в силу специфики задачи здесь  можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений8. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные · неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.
     Для контроля надо проверять, равна ли сумма чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце — потребности заказчика. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Решение транспортной задачи с открытой моделью  на примере метода минимального элемента
      Чтобы решить транспортную задачу с открытой моделью, необходимо преобразовать  её в модель закрытую, т.е. где  . Если суммарный груз превышает суммарные потребности, то тогда добавляют фиктивного потребителя, т.е в таблицу добавляют дополнительный столбец с нулевыми тарифами. Если объем поставок меньше чем объем груза, который нужен потребителю, в таблицу добавляется ещё одна строка с нулевыми показателями.
     Суть  метода заключается в том, что  из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел и . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
     Пример 
     Составить первоначальный опорный план методом  минимального элемента для транспортной задачи вида:
         2      3      4      15
         11      6      10      1
         8      9      3      3
         4      1      2      21
         10      20      10       
 
     Решение:
     Задача  сбалансирована.
     Строим  первоначальный опорный план методом  минимального элемента.
    Выясним минимальную стоимость перевозок. Первая перевозка будет осуществляться с пункта производства в пункт потребления и она составит максимально возможное число единиц продукта :. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2).
    Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта: , ;

    Четвертая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца и четвертой строки). .
    Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). .
    Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).
     Опорный план имеет вид; 

     10      5      0
     0      1      0
     0      3      0
     0      11      10
 
 
 
 
 
 
 
 
 
Заключение
     В работе изложены основные подходы и  метод решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки9. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
     Алгоритм  и методы решения транспортной задачи могут быть использованы при решении  некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи10. К таким задачам относятся следующие:
     - оптимальное закрепление за станками  операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;
     - оптимальные назначения, или проблема  выбора. Имеется m механизмов, которые  могут выполнять m различных работ  с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
     - задача о сокращении производства  с учетом суммарных расходов  на изготовление и транспортировку  продукции;
     - увеличение производительности  автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;
     - решение задач с помощью метода  запрещения перевозок. Используется  в том случае, если груз от  некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки11. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Список использованных источников
    Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.
    Баумоль У. Экономическая теория и исследование операций. – М.; Наука, 2004.
    Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.
    Боровков А.А. Математическая статистика. М.: Наука, 2004.
    Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 2004
    Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - СПБ: Издательство «Лань», 2003.
    Коршунов Д.А., Чернова Н.И. Сборник задач и упражнений по математической статистике. Новосибирск: Изд-во Института математики им. С.Л.Соболева СО РАН, 2001.
    Красс М. Математика для экономических специальностей. Учебник. 3-е изд., перераб и доп. М, Экономист, 2004.
    Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе: Учебник. – 3-е изд., исп. – М.: Дело, 2002.
    Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск, Высшая школа, 2005
    Пехелецкий И.Д. Математика: учебник для студентов. - М.: Академия, 2003.
    Павлова Т.Н, Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.
    Павлова Т.Н, Ракова О.А. Решение задач линейного программирования. Учебное пособие. - Димитровград, 2002.
 
 
 
 
 
Приложения
Приложения  А Таблица перевозок 

Пункты Отпр-ия
Пункты  назначения Запасы
Потребности
или

 
 
 
 
 
 
 
 
 
 
Приложение  Б Совокупность тарифов

и т.д.................


Пункты Отпр-ия
Пункты  назначения Запасы
 
 
 

Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.