Транспортная задача с избытком

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

1. Введение

2. Теоретическая часть

    2.1 История развития линейного программирования

    2.2 Понятие линейного программирования

          Постановка задач линейного программирования

    2.3 Основные понятия транспортной задачи

    2.4 Математическая модель

    2.5 Открытая и закрытая транспортная задача

    2.6 Незамкнутая транспортная задача с избытком

2.6.1 Транспортная задача с избытком запасов.

           2.6.2 Транспортная задача с избытком заявок

           2.6.3 Пример: транспортная задача линейного программирования. 

           2.6.4 Пример решения в Excel

3. Практическая часть

    3.1Незамкнутая транспортная задача с избытком

    3.2Решение транспортной задачи в Excel

4. Заключение

5. Литература

 

 

 

 

 

 

1. Введение

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

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

Предмет – Предметом исследования является транспортная задача. Объектом исследования выступает метод северо-западного угла.

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

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

Для реализации данной цели в работе необходимо решить следующие  задачи:

- рассмотреть транспортную  задачу, общую постановку, цели, задачи;

- изучить основные типы, виды моделей; 

- охарактеризовать методы  решения транспортной задачи;

- проанализировать метод северо-западного угла как метод решения транспортной задачи.

 

2. Теоретическая часть

2. 1 История развития линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач. [2]

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

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

       Основатель этого направления - Л.В. Канторович (1912 -1986), единственный Нобелевский лауреат (1975г.) по экономике. Толчком для разработки метода принятия экономических решений, известного сегодня как метод линейного программирования, послужила показавшаяся Канторовичу первоначально частной и элементарной практическая задача, с которой к нему обратились в 1938 году сотрудники Центральной лаборатории Ленинградского фанерного треста. Они попросили его порекомендовать им численный метод для расчета рационального плана загрузки имеющегося оборудования. Речь шла о комплексном выполнении пяти видов работ на лущильных станках восьми типов и различной производительности, так что выход продукции, казалось, зависел от чистой случайности - какая группа сырья на какой станок была направлена. 
       Решение данной задачи потребовало принципиально новых идей, позволяющих проводить целенаправленный перебор ряда необходимых комбинаций. Ядром открытия Канторовича являлась установленная им объективная связь задачи оптимального планирования с задачей определения соответствующих стоимостных показателей. На этой основе им были сформулированы признаки оптимальности, позволяющие предложить различные схемы целенаправленного перебора допустимых планов и систем стоимостных показателей. 
       Исследуя специальные задачи линейного программирования, Л.В.Канторович совместно с М.К.Гавуриным изучил в 1940 году транспортную задачу в матричной и сетевой постановках. Предложенный ими метод потенциалов и его обобщение в дальнейшем широко использовались в экономической практике. В 1942 году Канторович создал первый вариант своей капитальной монографии "Экономический расчет наилучшего использования ресурсов". [6]

2.2 Понятие линейного программирования

Постановка задач  линейного программирования

 

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

Линейное программирование – это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные  которой наложены линейные ограничения. Таким образом, задачи линейного  программирования относятся к задачам  на условный экстремум функции. По типу решаемых задач методы разделяются  на универсальные и специальные. С помощью универсальных методов  могут решаться любые задачи линейного  программирования (ЗЛП). Специальные  методы учитывают особенности модели задачи, ее целевой функции и системы  ограничений.[2]

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

       Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Общая форма задачи имеет вид: найти   при условиях

            

где

Здесь и далее нам удобнее  считать с и а_і вектор - строками, а x и b=(b₁,...,b_m)^T - вектор столбцами.

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

т.е. все переменные в любом  допустимом решении задачи должны принимать  неотрицательные значения (такие  переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I₂ = 0, а в другом - I₁ = 0.

Задача ЛП в канонической форме:

Задача ЛП в стандартной форме:

В обоих случаях А есть матрица размерности m x n, i -я строка которой совпадает с вектором а_i.

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

Задачи линейного программирования решаются несколькими методами:

1. графический метод;

2. симплексный метод;

3. двойственность в ЛП;

4.двойственный симплексный  метод.

 

  Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

1. рационального использования сырья и материалов;
2. задачи оптимального раскроя;
3. оптимизации производственной программы предприятий;
4. оптимального размещения и концентрации производства;
5. составления оптимального плана перевозок, работы транспорта  

    (транспортные задачи);

6. управления производственными запасами;
7. и многие другие, принадлежащие сфере оптимального планирования.

Методы решения задач  очень сложны и в связи с  этим транспортная задача относится  к отдельному классу. [6]

2.3 Основные понятия транспортной задачи

Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как  правило, распределение ресурсов, находящихся  у m производителей (поставщиков), по n потребителям этих ресурсов. На автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:

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

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

   Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году^[3]. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем^[4]. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича. [10]

 Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

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

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

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