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

Содержание

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]

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

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

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

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

Через конечное число шагов приходят к искомому оптимальному базисному  решению. [2]

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

В зависимости от методов подсчета алгебраических сумм тарифов для свободных клеток различают два метода отыскания оптимального решения транспортной задачи:

1.   Распределительный метод. При этом методе для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов.

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

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

Переменными (неизвестными) транспортной задачи являются x_ij ..,i-(=1,2, ..., k), j= 1,2, ..., n — объемы перевозок от каждого i -го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок:  
  
или

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

Система ограничений задачи состоит из двух групп уравнений. Первая группа из k уравнений описывает тот факт, что запасы всех kпоставщиков вывозятся полностью:

Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех nпотребителей:  
  
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:  
  
  
  
  
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.  
  
Такая задача называется задачей с правильным балансом, а ее модель — закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.  
Математическая формулировка транспортной задачи такова: найти переменные X =(x_ij ) задачи удовлетворяющие системе ограничений:  
  
условиям неотрицательности  и обеспечивающие минимум целевой функции.  
  
Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу A системы уравнений-ограничений задачи.

 
Сверху над каждым столбцом матрицы  указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы  ограничений. Каждый столбец матрицыA, соответствующий переменной х_ij.., является вектором-условием задачи и обозначается через A_ij. Каждый вектор имеет всего k+ nкоординат, и только две из них, отличные от нуля, равны единице. Первая единица вектора A_ij стоит на i-м месте, а вторая - на (k+j)-м  месте, т.е.

Таким образом в векторной  форме задача будет выглядеть  так:  
 [11]

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

Для решения транспортной задачи разработано несколько методов, каждый из которых отличается от другого  методом заполнения матрицы перевозок. 
          Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. [5]

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

Различают два типа транспортных задач: но критерию стоимости (план перевозок  оптимален, если достигнут минимум  затрат на его реализацию) и по критерию времени (план оптимален, если на его  реализацию затрачивается минимум  времени).

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

;

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

,

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

- мы имеем закрытую модель, а при условии

– открытую модель транспортной задачи.

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

Так же существуют одноэтапные  модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный  пункт”, например – склад.

План перевозок с указанием  запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:

Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю : совокупность этих величин образует матрицу (матрицу перевозок).

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

Совокупность тарифов  также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:

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

  [7]

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

В случае выполнения (1.4) (открытая модель) баланс транспортной задачи может  нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах  отправления превышает сумму  поданных заявок (транспортная задача  с избытком запасов):

å аi > å bj ( где i=1,...,m ; j=1,...,n );

          2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок):

                å аi < å bj ( где i=1,...,m ; j=1,...,n );

Рассмотрим последовательно  эти два случая:

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

Сведем её к ранее рассмотренной  транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов  назначения В1, B2, ... , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

bn+1 = å аi - å bj ( где i=1,...,m ; j=1,...,n ) ,

а стоимость перевозок  из всех пунктов отправления в  фиктивный пункт назначения bn+1 будем  считать равной нулю. Введением фиктивного пункта назначения B n+1 с его заявкой b n+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как  обычную транспортную задачу с правильным балансом. [8]

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

Эту задачу можно свести к обычной транспортной задаче с  правильным балансом, если ввести фиктивный  пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю. [9]

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

На складах №1, №2, №3 имеются  запасы продукции в количествах 90, 400 и 110 тонн соответственно. Продукцию необходимо доставить к потребителям П1, П2, П3, заявки которых составляют 140, 300 и 160 тонн. Склады и потребители расположены в различных районах города, поэтому расстояния между каждой парой из них различно. Соответственно транспортные расходы по перевозке товара с i-го склада к j-му потребителю также различны. Стоимость доставки единицы товара (одной тонны) от каждого склада к каждому потребителю в условных денежных единицах (у.д.е.) известна и представлена в табл.1.1.

Таблица 1.1.

Требуется составить план перевозок – определить количество груза x ij , которое должно быть вывезено из каждого i-го склада и доставлено к каждому j-му потребителю. При этом, с одной стороны, должна быть обеспечена доставка грузов всем потребителям в соответствии с их заявками, а с другой стороны, весь товар должен быть полностьювывезен со складов. План перевозок должен быть таким, чтобы совокупная стоимость транспортных издержек была минимальной.