Решение транспортной задачи распределительным методом с помощью языка программирования Turbo Pascal 7.0

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 30.12.2010
Размер файла 111,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Учреждение образования

«Брестский государственный университет имени А.С. Пушкина»

Кафедра математического моделирования

Курсовая работа

Решение транспортной задачи распределительным методом с помощью языка программирования Turbo Pascal 7.0

Брест, 2009

Содержание

Введение

1. Транспортная задача

1.1 Транспортная задача по критерию стоимости в матричной постановке

1.2 Опорный план транспортной задачи и его построения

1.2.1 Структура опорного плана

1.2.2 Способы построения начального опорного плана

1.2.3 Преобразование опорного плана в другой опорный план

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

2.1 Транспортная задача как частный случай общей распределительной задачи

2.2 Алгоритм распределительного метода

3. Примеры решения транспортных задач

Заключение

Список используемых источников

Введение

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

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

Задача заключается в отыскании такого плана перевозок продукции с Аi (i = ) складов в пункт назначения Bj (j = ), который потребовал бы минимальных затрат. Если j-ый потребитель получает единицу продукции (по прямой дороге) со i-ого склада, то возникают издержки сij, которые необходимо сократить.

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

Общая схема метода такова. В данном начальном опорном плане перевозок каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом. Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов Аi (i = ) и Bj (j = ), связанных основной коммуникацией, была равна cij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит cij, то данный план перевозок - оптимальное решение задачи. В противном случае указывают способ улучшения текущего плана транспортной задачи.

1. Транспортная задача

1.1 Транспортная задача по критерию стоимости в матричной постановке

Простейшая задача на перевозки по критерию стоимости формулируется следующим образом.

В m пунктах производства А1, … , Аm находится однородный продукт (уголь, картофель и т.д.) в количествах соответственно a1, …, am ед., который должен быть доставлен n потребителям B1, …, Bn в количествах b1, …, bn ед. Известны транспортные издержки cij (расходы), связанные с перевозкой единицы продукта из пункта Аi (i = ) в пункт Bj (j = ). Требуется составить такой план перевозок, который обеспечивал бы при минимальных транспортных издержках удовлетворение спроса всех пунктов потребления за счет распределения всего продукта, произведенного всеми пунктами поставки.

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

= . (1.1.1)

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

На практике условие (1.1.1), как правило, не выполняется. Однако при использовании рассматриваемых ниже методов решения предполагается, что задача закрытая. Поэтому надо знать, как открытую задачу формально преобразовать в закрытую.

Если суммарный запас продукта превышает общий спрос, т. е.

> ,

то в рассмотрение вводится фиктивный (n + 1)-й пункт потребления Bn+1 со спросом, равным небалансу, т.е.

= -,

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

Если же общий спрос потребителей больше суммарного запаса продукта, то вводится фиктивный (m + 1)-й пункт отправления Am+1 с запасом продукта

= -.

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

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

В таблице количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения, обозначено xij. Мы будем предполагать, что все xij 0, т.е. обратные перевозки (например, по рекламации) не рассматриваются.

Таблица

Постав-щик

Потребитель

Запас

груза

B1

B2

Bn

A1

c11

x11

c12

x12

c1n

x1n

a1

A2

c21

x21

c22

x22

c2n

x2n

a2

Am

cm1

xm1

cm2

xm2

cmn

xmn

am

Потребность в грузе

b1

b2

bn

Матрицу (cij) mn называют матрицей тарифов, а числа cij -- тарифами.

Планом транспортной задачи называют матрицу X = (xij)mn . Ее называют еще матрицей перевозок.

Составим математическую модель задачи. Целевая функция f, выражающая суммарные транспортные затраты, связанные с реализацией плана X перевозок, запишется в виде

f = c11 x11 + c12 x12 + … + cmn xmn =. (1.1.2)

Переменные xij должны удовлетворять ограничениям по запасам

xi1 + xi2 + … + xin = = ai (i =) (1.1.3)

и ограничениям по потребностям

x1j + x2j + … + xmj = = bj (j =). (1.1.4)

Поскольку обратные перевозки не предполагаются, то

0 (i =, j =). (1.1.5)

Таким образом, математически транспортная задача (1.1.2) -- (1.1.5) ставится следующим образом. Среди множества решений системы линейных уравнений (1.1.3), (1.1.4) и неравенств (1.1.5) найти такое решение (x*11; x*12; …; x*mn), которое доставляет минимум линейной функции (1.1.2). Отсюда видно, что транспортная задача является задачей линейного программирования и ее можно решать симплекс-методом. Однако специфические особенности системы ограничительных уравнений (1.1.3), (1.1.4) позволили разработать для транспортной задачи более простые методы решения.

Эти особенности состоят в следующем:

1) коэффициенты при переменных во всех уравнениях равны либо единице, либо нулю;

2) каждая переменная встречается в двух и только двух уравнениях: один раз в системе ограничений по запасам и один раз в системе ограничений по потребностям;

3)система уравнений симметрична относительно всех переменных xij.

1.2 Опорный план транспортной задачи и его построение

1.2.1 Структура опорного плана. Важное для приложений значение имеет приведенная ниже теорема

Ранг матрицы системы ограничительных уравнений транспортной задачи (1.1.2) - (1.1.5) на единицу меньше числа уравнений, т. е. r = m + n - 1.

Система ограничительных уравнений содержит mn переменных и m + n уравнений. Из сформулированной теоремы следует, что каждый опорный план задачи имеет m + n - 1 базисных переменных и mn - (m + n - 1) свободных переменных, равных нулю.

План перевозок будем строить непосредственно в транспортной таблице. Если переменная xij принимает значение aij, отличное от нуля, т.е. xij = aij 0, то в соответствующую клетку (i; j) таблицы будем вписывать это значение; если же xij = 0, то клетку (i; j) оставляем свободной. Согласно формулированной теореме, каждый опорный план будет "загружать" m + n - 1 клеток, а остальные останутся свободными. Это не единственное требование к опорному плану, требование связано с циклами в транспортной таблице.

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

Упомянутый набор клеток можно записать в виде

(i1; j1) (i1; j2) (i2; j2) … (is; js) (is; j1).

Графическим изображением цикла является замкнутая ломаная линия (контур), звенья которой расположены только в строках и столбцах таблицы. Каждое звено соединяет две и только две соседние клетки цикла. Таким образом, план транспортной задачи является опорным тогда и только тогда, когда из занятых им m + n - 1 клеток нельзя образовать ни одного цикла.

При решении транспортной задачи будем использовать прием последовательного улучшения плана, предусматривающий следующие этапы: 1) построение начального опорного плана; 2) оценка этого плана; 3) переход от имеющегося опорного плана к новому опорному плану с меньшими транспортными затратами.

1.2.2 Способы построения начального опорного плана

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются аi(q), а текущих неудовлетворенных потребностей -- bj(q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем аi(0)= аi, bj(0)= bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: хi,j=min{аi(q), bj(q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

аi(q+1)= аi(q) - xi,j, bj(q+1)= bj(q) - xi,j

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi(q+1)= 0 или bj(q+1)= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т. е. переместиться к следующей клетке вниз по столбцу. Если же bj(q+1) = 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (аi(q)=bj(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

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

1.2.3 Преобразование опорного плана в другой опорный план

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

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

2.1 Транспортная задача как частный случай общей распределительной задачи

Транспортная задача ставится следующим образом: имеется m пунктов отправления А1, А2 , ..., Аm , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, ... , аm единиц. Имеется n пунктов назначения В1 , В2 , ... , Вn подавшие заявки соответственно на b1 , b2 , ... , bn единиц груза. Известны стоимости Сi,j перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj . Все числа Сi,j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Решение транспортной задачи начинается с нахождения опорного плана. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю.

Составляя план по способам минимальных стоимостей в отличие от плана по способу “северо-западного угла” мы учитываем стоимости перевозок Ci,j, но все же не можем утверждать, что составленный нами план является оптимальным. Циклом в транспортной задаче мы будем называть несколько занятых клеток, соединённых замкнутой ломанной линией, которая в каждой клетке совершает поворот на 90.

Существует несколько вариантов цикла:

1.) 2.) 3.)

Нетрудно убедиться, что каждый цикл имеет чётное число вершин и значит, чётное число звеньев (стрелок). Условимся отмечать знаком “+” те вершины цикла, в которых перевозки необходимо увеличить, а знаком “-“ те вершины , в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называть “означенным”. Перенести какое-то количество единиц груза по означенному циклу -- это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется. По прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце -- заявке этого столбца. Таким образом, при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком “+”, а в отрицательных со знаком “-“. Обозначим цену цикла через . При перемещении одной единицы груза по циклу стоимость перевозок увеличивается на величину . При перемещении по нему k единиц груза стоимость перевозок увеличиться на k. Очевидно, для улучшения плана имеет смысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждый раз, когда нам удаётся совершить такое перемещение, стоимость плана уменьшается на соответствующую величину k. Так как перевозки не могут быть отрицательными, мы будем пользоваться только такими циклами, отрицательные вершины которых лежат в базисных клетках таблицы, где стоят положительные перевозки. Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный план достигнут.

Метод последовательного улучшения плана перевозок и состоит в том, что в таблице отыскиваются циклы с отрицательной ценой, по ним перемещаются перевозки, и план улучшается до тех пор, пока циклов с отрицательной ценой уже не останется. При улучшении плана циклическими переносами, как правило, пользуются приёмом, заимствованным из симплекс-метода: при каждом шаге (цикле) заменяют одну свободную переменную на базисную, то есть заполняют одну свободную клетку и взамен того освобождают одну из базисных клеток. При этом общее число базисных клеток остаётся неизменным и равным m + n - 1 . Этот метод удобен тем, что для него легче находить подходящие циклы.

Можно доказать, что для любой свободной клетке транспортной таблице всегда существует цикл и притом единственный, одна из вершин которого лежит в этой свободной клетке, а все остальные в базисных клетках. Если цена такого цикла, с плюсом в свободной клетке, отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза k, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки).

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

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

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

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

(2.1.4)

Обозначим алгебраическую сумму тарифов следующим образом:

. (2.1.5)

Тогда равенство (2.1.4) запишется в виде:

. (2.1.6)

Из равенства (2.1.5) видно, что величина зависит от значений тарифов cij и однозначно определяется структурой цикла клетки (k;s). Поэтому называется оценкой свободной клетки (k;s).

Из равенства (2.1.6) следует, что < 0, если < 0(всегда величина неотрицательная), т.е. если оценка свободной клетки отрицательная, то ее следует загружать. Такие клетки называются перспективными. Если же оценки всех свободных клеток неотрицательные, то содержащийся в распределительной таблице опорный план является оптимальным. Если в распределительной таблице, содержащей оптимальный план, имеются свободные клетки с нулевыми оценками, то задача имеет не единственный опорный план. Загружая свободную клетку с нулевой оценкой, можно найти еще один оптимальный план.

2.2 Алгоритм распределительного метода

Ниже приведен алгоритм распределительного метода

1. Условия задачи записывают в форме распределительной таблицы.

2. Сравнивают общий запас груза с суммарным спросом и случае нарушения равенства вводят в рассмотрение фиктивного поставщика (потребителя).

3. Строят начальный опорный план.

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

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

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

3. Примеры решения транспортных задач

3.1 Задача

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

. Вектор запасов А = (45, 35, 70, 60). Вектор заявок

В = (40, 35, 55, 60).

Решение

= 210, = 190, > .

Таким образом, возникает задача открытого типа. Придется ввести в рассмотрение фиктивного потребителя В5 с заявкой равной 20 и нулевыми тарифами. Составим экономико-математическую модель, обозначив через xij объем поставки i-м поставщиком j-му потребителю (i = , j = ). Целевую функцию f надо минимизировать. Клетки загружаем способом "минимального элемента".

Данные задачи можно записать в виде таблицы:

B1

B2

B3

B4

B5

A1

5

6

5

15

3

30

0

45

A2

7

3

5

10

7

- 30

0

35

A3

2

40

5

30 -

12

6

0

70

A4

9

8

7

40

10

0

20

60

40

35

55

60

20

Загружено клеток m + n - 1 = 4 + 5 - 1 = 8, так что план невырожденный. Для исследования его на оптимальность составляем систему уравнений (2.1.4), а затем равенство запишется в виде (2.1.6) для определения потенциалов.

11 == 5 - 3 + 7 - 3 + 5 - 2 = 9

12 = = 6 - 3 + 7 - 3 = 7

15 = = 0 - 0 + 7 - 5 = 2

21 = = 7 -3 + 5 - 2 = 7

23 = = 10 - 5 + 3 -7 =1

25 = = 0 - 0 + 7 - 5 + 3 = -2

33 = =12 - 5 + 3 - 7 + 3 - 5 = 1

34 = =6 - 5 + 3 - 7 = -3

35 = = 0 - 0 + 7 - 5 + 3 - 7 + 3 - 5 = -4

41 = =9 - 2 + 5 - 3 + 7 - 3 + 5 - 7 = 7

42 = = 8 - 3 + 7 - 3 +5 -7 =7

44 = = 10 - 3 + 5 - 7 = 5

Среди оценок есть отрицательные, поэтому план неоптимальный и его следует преобразовать. Выбираем клетку (3; 4) с наибольшей по абсолютной величине отрицательной оценкой.

Исследуя этот план аналогично предыдущему, находим потенциалы, а по ним - оценки свободных клеток.

B1

B2

B3

B4

B5

A1

5

6

5

15 -

3

30

0

45

A2

7

3

35

10

7

0

35

A3

2

40

5

0

12

6

30 -

0

70

A4

9

8

7

40

10

0

- 20

60

40

35

55

60

20

11 = = 5 -3 + 6 - 2 = 6

12 = = 6 - 3 + 6 - 5 = 4

15 = = 0 - 0 + 7 - 5 = 2

21 = = 7 - 3 + 5 - 2 = 7

23 = = 10 - 3 + 5 - 6 + 3 - 5= 4

24 = = 7 - 6 + 5 - 3 = 3

25 = = 0 - 0 + 7 - 5 + 3 - 6 + 5 - 3 = 1

33 = = 12 - 5 + 3 - 6 = 4

35 = = 0 - 0 + 7 - 5 + 3 - 6 = -1

41 = =9 - 2 + 6 - 3 + 5 - 7 = 8

42 = =8 - 5 + 6 - 3 + 5 - 7 =4

44 = = 10 - 7 + 5 - 3 = 5

Среди оценок есть одна отрицательная, поэтому план неоптимальный и его следует улучшить, загружая клетку (3; 5). Исследуя этот план на оптимальность, находим потенциалы и оценки свободных клеток.

B1

B2

B3

B4

B5

A1

5

6

5

3

45

0

45

A2

7

3

35

10

7

0

35

A3

2

40

5

0

12

6

15

0

15

70

A4

9

8

7

55

10

0

5

60

40

35

55

60

20

11 = 5 - 3 + 6 - 2= 6

12 = 6 - 3 + 6 - 5= 4

13 = 5 - 3 + 6 - 0 + 0 -7= 1

15 = 0 - 0 + 6 - 3= 3

21 = 7 - 3 + 5 - 2= 7

23 = 10 - 3 + 5 - 0 + 0 - 7 = 5

24 = 7 - 6 + 5 - 3= 3

25 = 0 - 0 + 5 - 3= 2

33 = 12 - 0 + 0 - 7 = 5

41 = 9 - 0 + 0 - 2= 7

42 = 8 - 0 + 0 - 5=3

44 = 10 - 0 + 0 - 6= 4

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

f = 45*3 + 35*3 + 40*2 + 0*5 + 15*6 + 15*0 + 55*7 + 0*5 = 135 + 105 +

+ 80 + 90 + 385 = 795

3.2 Задача

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

. Вектор запасов А = (120, 85, 75). Вектор заявок

В = (90, 70, 60, 80).

Решение

= 280, = 300, < .

Таким образом, задача открытого типа. Введем в рассмотрение фиктивного поставщика А4 с запасом равным 20 и нулевыми тарифами. Составим экономико-математическую модель, обозначив через xij объем поставки i-м поставщиком j-му потребителю (i = , j = ). Целевую функцию f надо минимизировать. Клетки загружаем способом "северо-западного угла".

Данные задачи можно записать в виде таблицы:

B1

B2

B3

B4

A1

3

90

12

30 -

7

15

120

A2

4

6

40

8

- 45

9

85

A3

5

10

6

15

7

60

75

A4

0

0

0

0

20

20

90

70

60

80

Загружено клеток m + n - 1 = 4 + 4 - 1 = 7, так что план невырожденный. Для исследования его на оптимальность составляем систему уравнений (2.1.4), а затем равенство запишется в виде (2.1.6) для определения потенциалов.

13 = =7 - 12 + 6 - 8 = -7

14 = =15 - 7 + 6 - 8 + 6 - 12 = 0

21 = =4 - 3 + 12 - 6 = 7

24 = =9 - 7 + 6 - 8 = 0

31 = =5 - 3 + 12 - 6 + 8 - 6 = 10

32 = = 10 - 6 + 8 - 6= 6

41 = =0 - 3 + 12 - 6 + 8 -6 + 7 - 0 = 12

42 = =0 - 12 + 6 - 8 + 6 - 7 + 0 = 3

43 = =0 - 6 + 7 - 0 = 1

Среди оценок есть одна отрицательная, поэтому план неоптимальный и его следует улучшить, загружая клетку (1; 3). Исследуя этот план на оптимальность, находим потенциалы и оценки свободных клеток.

B1

B2

B3

B4

A1

3

90

12

7

30

15

120

A2

4

6

70

8

15

9

85

A3

5

10

6

15

7

60

75

A4

0

0

0

0

20

20

90

70

60

80

12 = 12 - 7 + 8 - 6 = 7

14 = 15 - 7 + 6 - 7 = 7

21 = 4 - 3 + 7 - 8 = 0

24 = 9 - 7 + 6 - 8= 0

31 = 5 - 3 + 7 - 6= 3

32 = 10 - 6 + 8 - 6= 6

41 = 0 - 3 + 7 - 6 + 7 - 0= 5

42 = 0 - 6 + 8 - 6 + 7 - 0= 3

43 = 0 - 6 + 7 - 0= 1

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

f = 90*3 + 30*7 + 70*6 + 15*8 + 15*6 + 60*7 = 270 + 210 + 420 + 120 +

+ 90 +420 = 1530

3.3 Задача

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

. Вектор запасов А = (110, 75, 95). Вектор заявок

В = (60, 60, 60, 100).

Решение

= 280, = 280, = .

Таким образом, задача закрытого типа. Составим экономико-математическую модель, обозначив через xij объем поставки i-м поставщиком j-му потребителю (i = , j = ). Целевую функцию f надо минимизировать. Клетки загружаем способом "северо-западного угла".

Данные задачи можно записать в виде таблицы:

B1

B2

B3

B4

A1

5

60

10

50 -

8

4

110

A2

7

5

10

11

- 60

6

5

75

A3

6

15

13

10

95

95

60

60

60

100

Загружено клеток m + n - 1 = 4 + 3 - 1 = 6, так что план невырожденный. Для исследования его на оптимальность составляем систему уравнений (2.1.4), а затем равенство запишется в виде (2.1.6) для определения потенциалов.

13 = = 8 - 11 + 5 - 10 = -8

14 = = 4 - 6 + 5 - 10= -7

21 = =7 - 5 + 10 - 5= 7

31 = = 6 - 5 + 10 - 5 + 6 - 10 = 2

32 = = 15 - 5 + 6 - 10= 6

33 = = 13 - 11 + 6 - 10= -2

Среди оценок есть отрицательные, поэтому план неоптимальный и его следует преобразовать. Выбираем клетку (1; 3) с наибольшей по абсолютной величине отрицательной оценкой.

Исследуя этот план аналогично предыдущему, находим потенциалы, а по ним - оценки свободных клеток.

транспортный распределительный алгоритм

B1

B2

B3

B4

A1

5

60 -

10

8

50

4

110

A2

7

5

60

11

10 -

6

5

75

A3

6

15

13

10

- 95

95

60

60

60

100

12 = = 10 - 8 + 11 - 5= 8

14 = = 4 - 6 + 11 - 8 = 1

21 = = 7 - 5 + 8 - 11= -1

31 = = 6 - 5 + 8 - 11 + 6 - 10= -6

32 = = 15 - 5 + 6 - 10= 6

33 = = 13 - 11 + 6 - 10= -2

Среди оценок есть отрицательные. Выбираем клетку (3; 1) с наибольшей по абсолютной величине отрицательной оценкой. Исследуя этот план на оптимальность, находим потенциалы и оценки свободных клеток.

B1

B2

B3

B4

A1

5

50 -

10

8

60

4

110

A2

7

5

60

11

6

15

75

A3

6

10

15

13

10

- 85

95

60

60

60

100

12 = = 10 - 5 + 6 - 10 + 6 - 5= 2

14 = = 4 - 10 + 6 - 5= -5

21 = = 7 - 6 + 10 - 6= 5

23 = = 11 - 6 + 10 - 6 + 5 - 8= 6

32 = = 15 - 5 + 6 - 10= 6

33 = = 13 - 8 + 5 - 6= 4

Среди оценок есть одна отрицательная, поэтому план неоптимальный и его следует улучшить, загружая клетку (1; 4).

B1

B2

B3

B4

A1

5

10

8

60 -

4

50

110

A2

7

5

60

11

6

15

75

A3

6

60

15

13

10

- 35

95

60

60

60

100

11 = 5 - 4 + 10 - 6= 5

12 = 10 - 4 + 6 - 5= 7

21 = 7 - 6 + 10 - 6= 5

23 = 11 - 8 + 4 - 6= 1

32 = 15 - 5 + 6 - 10= 6

33 = 13 - 8 + 4 - 10= -1

Среди оценок одна отрицательная, поэтому загружаем клетку (3; 3).

B1

B2

B3

B4

A1

5

10

8

25

4

85

110

A2

7

5

60

11

6

15

75

A3

6

60

15

13

35

10

95

60

60

60

100

11 = 5 - 8 + 13 - 6= 4

12 = 10 - 4 + 6 - 5= 7

21 = 7 - 6 + 4 - 8 + 13 - 6= 4

23 = 11 - 8 + 4 - 6 = 1

32 = 15 - 13 + 8 - 4 + 6 - 5= 7

34 = 10 - 13 + 8 - 4= 1

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

f = 25*8 + 85*4 + 60*5 + 15*6 + 60*6 + 35*13 = 200 + 340 + 300 + 90 +

+ 360 + +455 = 1745

3.4 Задача

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

. Вектор запасов А = (35, 40, 40). Вектор заявок В =

= (25, 25, 55).

Решение

= 115, = 105, > .

Таким образом, возникает задача открытого типа. Придется ввести в рассмотрение фиктивного потребителя В4 с заявкой равной 10 и нулевыми тарифами. Составим экономико-математическую модель, обозначив через xij объем поставки i-м поставщиком j-му потребителю (i = , j = ). Целевую функцию f надо минимизировать. Клетки загружаем способом "северо-западного угла".

Данные задачи можно записать в виде таблицы:

B1

B2

B3

B4

A1

6

25 -

6

10

8

0

35

A2

5

6

15 -

7

25

0

40

A3

4

7

10

- 30

0

10

40

25

25

55

10

Загружено клеток m + n - 1 = 4 + 3 - 1 = 6, так что план невырожденный. Для исследования его на оптимальность составляем систему уравнений (2.1.4), а затем равенство запишется в виде (2.1.6) для определения потенциалов.

13 = = 8 - 7 + 6 - 6= 1

14 = = 0 - 0 + 10 - 7 + 6 - 6 = 3

21 = = 5 - 6 + 6 - 6 = -1

24 = = 0 - 0 + 10 - 7 = 3

31 = = 4 - 6 + 6 - 6 + 7 - 10= -5

32 = = 7 - 6 + 7 - 10= -2

Среди оценок есть отрицательные, поэтому план неоптимальный и его следует улучшить, загружая клетку (3;1). Исследуя этот план на оптимальность, находим потенциалы и оценки свободных клеток.

B1

B2

B3

B4

A1

6

10 -

6

25

8

0

35

A2

5

6

7

40

0

40

A3

4

15

7

10

- 15

0

10

40

25

25

55

10

13 =8 - 10 + 4 - 6 = -4

14 =0 - 0 + 4 - 6= -2

21 =5 - 7 + 10 - 4= 4

22 =6 - 7 + 10 - 4 + 6 - 6= 5

24 =0 - 0 + 10 - 7= 3

32 =7 - 6 + 6 -4= 3

Среди оценок есть отрицательные, поэтому загружаем клетку (1; 3).

B1

B2

B3

B4

A1

6

6

25 -

8

10

0

35

A2

5

6

7

40

0

40

A3

4

25

7

10

- 5

0

10

40

25

25

55

10

11 = 6 - 8 + 10 - 4= 5

14 = 0 - 0 + 10 - 8= 2

21 = 5 - 7 + 10 - 4= 5

22 = 6 - 6 + 8 - 7= 1

24 = 0 - 0 + 10 - 7= 3

32 = 7 - 6 + 8 - 10= -1

Есть одна отрицательная оценка 32.

B1

B2

B3

B4

A1

6

6

20

8

15

0

35

A2

5

6

7

40

0

40

A3

4

25

7

5

10

0

10

40

25

25

55

10

11 = 6 - 6 + 7 - 4= 3

14 = 0 - 0 + 7 - 6= 1

21 = 5 - 7 + 8 - 6 + 7 - 4= 3

22 = 6 - 6 + 8 - 7= 1

24 = 0 - 0 + 7 - 6 + 8 - 7= 2

33 = 10 - 7 + 6 - 8= 1

Отрицательных оценок больше нет, таким образом, план оптимальный. Целевая функция:

f = 20*6 + 15*8 + 40*7 + 25*4 + 5*7 = 120 + 120 + 280 + 100 + 35 = 655

3.5 Задача

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

. Вектор запасов А = (70, 70, 110). Вектор заявок

В = (70, 90, 70, 60).

Решение

= 250, = 290, < .

Таким образом, задача открытого типа. Введем в рассмотрение фиктивного поставщика А4 с запасом равным 40 и нулевыми тарифами. Составим экономико-математическую модель, обозначив через xij объем поставки i-м поставщиком j-му потребителю (i = , j = ). Целевую функцию f надо минимизировать. Клетки загружаем способом "северо-западного угла".

Данные задачи можно записать в виде таблицы:

B1

B2

B3

B4

A1

20

70 -

13

8

0

11

70

A2

15

9

70

17

18

70

A3

21

19

20

15

70 -

13

20

110

A4

0

0

0

0

- 40

40

70

90

70

60

Загружено клеток m + n - 1 = 4 + 4 - 1 = 7, так что план невырожденный. Для исследования его на оптимальность составляем систему уравнений (2.1.4), а затем равенство запишется в виде (2.1.6) для определения потенциалов.

12 == 13 - 8 + 15 - 19= 1

14 = = 11 - 13 + 15 - 8= 5

21 = = 15 - 9 + 19 - 15 + 8 - 20= -2

23 == 17 - 15 + 19 - 9= 12

24 = = 18 - 13 + 19 - 9= 15

31 = = 21 - 15 + 8 - 20= -6

41 = = 0 - 0 + 13 - 15 + 8 - 20= -14

42 = = 0 - 0 + 13 - 19= -6

43 = =0 - 0 + 13 - 15= -2

Среди оценок есть отрицательные, поэтому план неоптимальный и его следует преобразовать. Выбираем клетку (4; 1) с наибольшей по абсолютной величине отрицательной оценкой.

Исследуя этот план аналогично предыдущему.

B1

B2

B3

B4

A1

20

30 -

13

8

40

11

70

A2

15

9

70

17

18

70

A3

21

19

20

15

- 30

13

60

110

A4

0

40

0

0

0

40

70

90

70

60

12 = = 13 - 19 + 15 - 8 = 1

14 = = 11 - 13 + 15 - 8= 5

21 = = 15 - 9 + 19 - 15 + 8 - 20 = -2

23 = = 17 - 15 + 19 - 9= 12

24 = = 18 - 13 + 19 - 9= 15

31 = = 21 - 15 + 8 - 20= -6

42 = = 0 - 19 + 15 - 8 + 20 - 0= 12

43 = = 0 - 8 + 20 - 0= 8

44 = = 0 - 13 + 15 - 8 + 20 - 0= 14

Выбираем клетку (3;1) с наибольшей по абсолютной величине отрицательной оценкой. Находим потенциалы и оценки свободных клеток.

B1

B2

B3

B4

A1

20

13

8

70

11

70

A2

15

9

70

17

18

70

A3

21

30

19

20

15

0

13

60

110

A4

0

40

0

0

0

40

70

90

70

60

11 =20 - 8 + 15 - 21= 6 21 =15 - 9 + 19 - 21= 4

12 =13 - 8 + 15 - 19= 1 23 =17 - 15 + 19 - 9= 12

14 =11 - 13 + 15 - 8= 5 24 =18 - 13 + 19 - 9= 15

42 =0 - 19 + 21 - 0 = 2 44 =0 - 13 + 21 - 0= 8

43 =0 - 15 + 21 - 0= 6

Отрицательных оценок больше нет, таким образом, план оптимальный. Целевая функция:

f = 70*8 + 70*9 + 30*21 + 20*19 + 13*60 = 560 + 630 + 630 + 380 + 780 =

= 2980

3.6 Задача

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

. Вектор запасов А = (40, 50, 60). Вектор заявок

В = (60, 50, 40, 20, 20).

Решение

= 150, = 190, < .

Таким образом, задача открытого типа. Введем в рассмотрение фиктивного поставщика А4 с запасом равным 40 и нулевыми тарифами. Составим экономико-математическую модель, обозначив через xij объем поставки i-м поставщиком j-му потребителю (i = , j = ). Целевую функцию f надо минимизировать. Клетки загружаем способом "минимального элемента".

Данные задачи можно записать в виде таблицы:

B1

B2

B3

B4

B5

A1

7

0

13

8

40

9

11

- 0

40

A2

15

9

50

17

10

0

9

50

A3

9

60

11

12

13

14

60

A4

0

0

0

0

20 -

0

20

40

60

50

40

20

20

Загружено клеток m + n - 1 = 4 + 5 - 1 = 8, так что план невырожденный. Для исследования его на оптимальность составляем систему уравнений (2.1.4), а затем равенство запишется в виде (2.1.6) для определения потенциалов.

12 = = 13 - 9 + 10 - 0 + 0 - 11= 3

14 = = 9 - 11 + 0 - 0= -2

21 = =15 - 10 + 0 - 0 + 11 - 7= 9

23 = = 17 - 10 + 0 - 0 + 11 - 8 = 10

25 = = 9 - 0 + 0 - 10 = -1

32 = = 11 - 9 + 10 - 0 + 0 - 11 + 7 -

- 9 = -1

33 = = 12 - 8 + 7 - 9= 2

34 = = 13 - 0 + 0 - 11 + 7 - 9= 0

35 = = 14 - 11 + 7 - 9= 1

41 = = 0 - 0 + 11 - 7 = 4

42 = = 0 - 0 + 10 - 9= 1

43 = = 0 - 0 + 11 - 8 = 3

Среди оценок есть отрицательные, поэтому план неоптимальный и его следует преобразовать. Выбираем клетку (1; 4) с наибольшей по абсолютной величине отрицательной оценкой.

Исследуя этот план аналогично предыдущему.

B1

B2

B3

B4

B5

A1

7

0

13

8

40

9

0

11

40

A2

15

9

50

17

10

0 -

9

50

A3

9

60

11

12

13

14

60

A4

0

0

0

0

20

0

- 20

40

60

50

40

20

20

12 = 13 - 9 + 10 - 9= 5 33 = 12 - 8 + 7 - 9= 2

15 = 11 - 0 + 0 - 9 = 2 34 = 13 - 9 + 7 - 9= 2

21 = 15 - 10 + 9 - 7= 7 35 = 14 - 0 + 0 - 9 + 7 - 9= 3

23 = 17 - 10 + 9 - 8= 8 41 = 0 - 9 + 7 - 0= 2

25 = 9 - 0 + 0 - 10= -1 42 = 0 - 0 + 10 - 9=1

32 = 11 - 9 + 10 - 9 + 7 - 9= 1 43 = 0 - 0 + 9 - 8= 1

Выбираем клетку (2; 5), т. к. оценка 25 отрицательная.

B1

B2

B3

B4

B5

A1

7

0

13

8

40

9

0

11

40

A2

15

9

50

17

10

9

0

50

A3

9

60

11

12

13

14

60

A4

0

0

0

0

20

0

20

40

60

50

40

20

20

12 = 13 - 9 + 9 - 0 + 0 - 9= 4

15 = 11 - 0 + 0 - 9= 2

21 = 15 - 9 + 0 - 0 + 9 - 7= 8

23 = 17 - 9 + 0 - 0 + 9 - 8= 9

24 = 10 - 9 + 0 - 0 = 1

32 = 11 - 9 + 9 - 0 + 0 - 9 + 7 - 9= 0

33 = 12 - 8 + 7 - 9 = 2

34 = 13 - 9 + 7 - 9= 2

35 = 14 - 0 + 0 - 9 + 7 - 9= 3

41 = 0 - 0 + 9 - 7= 2

42 = 0 - 0 + 9 - 9=0

43 = 0 - 0 + 11 - 9= 1

Отрицательных оценок нет, таким образом, план оптимальный. Целевая функция:

f = 40*8 + 50*9 + 60*9 = 320 + 450 + 540 = 1310

3.7 Задача

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

. Вектор запасов А = (48, 30, 27, 20). Вектор заявок

В = (18, 27, 42, 12, 26).

Решение

= 125, = 125, = .

Таким образом, задача закрытого типа. Составим экономико-математическую модель, обозначив через xij объем поставки i-м поставщиком j-му потребителю (i = , j = ). Целевую функцию f надо минимизировать. Клетки загружаем способом "минимального элемента".

Данные задачи можно записать в виде таблицы:

B1

B2

B3

B4

B5

A1

10

8

14

5

22

6

12

9

48

A2

6

7

13 -

8

6

5

17

30

A3

8

18

7

10

8

7

- 9

27

A4

7

5

4

20

6

8

20

18

27

42

12

26

Загружено клеток m + n - 1 = 4 + 5 - 1 = 8, так что план невырожденный. Для исследования его на оптимальность составляем систему уравнений (2.1.4), а затем равенство запишется в виде (2.1.6) для определения потенциалов.

11 = = 10 - 8 + 7 - 5 + 7 - 8= 3

15 = = 9 - 5 + 7 - 8= 3

21 = = 6 - 5 + 7 - 8= 0

23 = = 8 - 5 + 8 - 7= 4

24 = = 6 - 6 + 8 - 7 = 1

32 == 7 - 7 + 5 - 7= -2

33 = = 10 - 7 + 5 - 7 + 8 - 5= 4

34 = = 8 - 7 + 5 - 7 + 8 - 6= 1

41 = = 7 - 8 + 7 - 5 + 7 - 8 + 5 - 4= 1

42 = = 5 - 4 + 5 - 8= -2

44 = = 6 - 6 + 5 - 4= 1

45 = = 8 - 5 + 7 - 8 + 5 - 4= 3

Среди оценок есть отрицательные, поэтому план неоптимальный и его следует преобразовать. Выбираем клетку (3; 2) с наибольшей по абсолютной величине отрицательной оценкой.

Исследуя этот план аналогично предыдущему.

B1

B2

B3

B4

B5

A1

10

8

14 -

5

22

6

12

9

48

A2

6

7

4

8

6

5

26

30

A3

8

18

7

9

10

8

7

27

A4

7

5

4

- 20

6

8

20

18

27

42

12

26

11 = 10 - 8 + 7 - 8 = 1

15 = 9 - 5 + 7 - 8= 3

21 = 6 - 7 + 7 - 8= -2

23 = 8 - 5 + 8 - 7= 4

24 = 6 - 6 + 8 - 7= 1

33 = 10 - 5 + 8 - 7= 6

34 = 8 - 6 + 8 - 7= 3

35 = 7 - 5 + 7 - 7= 2

41 = 7 - 8 + 7 - 8 + 5 - 4= -1

42 = 5 - 4 + 5 - 8= -2

44 = 6 - 6 + 5 - 4=1

45 = 8 - 5 + 7 - 8 + 5 - 4= 3

Выбираем клетку (4; 2) с наибольшей по абсолютной величине отрицательной оценкой. Находим потенциалы и оценки свободных клеток.

B1

B2

B3

B4

B5

A1

10

8

5

36

6

12

9

48

A2

6

7

- 4

8

6

5

26

30

A3

8

18 -

7

9

10

8

7

27

A4

7

5

14

4

6

6

8

20

18

27

42

12

26

11 = 10 - 5 + 4 - 5 + 7 - 8= 3

12 = 8 - 5 + 4 - 5= 2

15 = 9 - 5 + 7 - 5 + 4 - 5= 5

21 = 6 - 7 + 7 - 8= -2

23 = 8 - 4 + 5 - 7= 2

24 = 6 - 6 + 5 - 4 + 5 - 7= -1

33 = 10 - 4 + 5 - 7= 4

34 = 8 - 7 + 5 - 4 + 5 - 6= 1

35 = 7 - 5 + 7 - 7= 2

41 = 7 - 8 + 7 - 5= 1

44 = 6 - 6 + 5 - 4=1

45 = 8 - 5 + 7- 5= 5

Выбираем клетку (2; 1), т. к. оценка 21 отрицательная.

B1

B2

B3

B4

B5

A1

10

8

5

36

6

12

9

48

A2

6

4

7

8

6

5

26

30

A3

8

14

7

13

10

8

7

27

A4

7

5

14

4

6

6

8

20

18

27

42

12

26

11 = 10 - 5 + 4 - 5 + 7 - 8 + 6 = 3

12 = 8 - 5 + 4 - 5 = 2

15 = 9 - 5 + 6 - 8 + 7 - 5 + 4 - 5= 3

22 = 7 - 7 + 8 - 6 = 2

23 = 8 - 6 + 8 - 7 + 5 - 4 = 4

24 = 6 - 6 + 5 - 4 + 5 - 7 + 8 - 6= 1

33 = 10 - 4 + 5 - 7= 4

34 = 8 - 6 + 5 - 4 + 5 - 7 = 1

35 = 7 - 5 + 6 - 8 = 0

41 = 7 - 5 + 7 - 8 = 1

44 = 6 - 6 + 5 - 4 = 1

45 = 8 - 5 + 6 - 8 + 7 - 5 = 3

Отрицательных оценок больше нет, таким образом, план оптимальный. Целевая функция:

f = 36*5 + 12*6 + 4*6 + 26*5 + 14*8 + 13*7 + 14*5 + 6*4 = 180 + 72 +

+ 24 +130 + 112 + 91 + 70 + 24 = 703

Заключение

Одним из распространенных методом решения транспортных задач является распределительный метод. Решение задачи распределительным методом производиться поэтапно:

разработку начального плана (опорного решения);

расчет потенциалов;

проверку плана на оптимальность;

поиск максимального звена неоптимальности;

составление контура перераспределения ресурсов;

определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;

получение нового плана.

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

Для транспортной задачи существует несколько способов отыскания начального плана (опорного решения): способ северо-западного угла; способ минимального элемента и т. д.

Список используемых источников

1. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. - М.: Высш. шк., 2001. - 129 с.

2. Безгинов А.Н. Экономико-математические модели в землеустройстве (линейные модели). - М.: ГУЗ, 1994. - 96 с.

3. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. - М.: Наука, 1976. - 103с.

4. Карманов В.Г. Математическое программирование. - М.: Наука, 1986. - 74с.

5. Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 1986

6. Геронимус Б.А. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 1982

7. Кузнецов Ю.Н., Кузубов В.И., Волощснко А.Б. Математическое программирование. М.: Высшая школа, 1980

Размещено на Allbest.ru


Подобные документы

  • Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.

    курсовая работа [1000,7 K], добавлен 23.06.2012

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

    курсовая работа [2,0 M], добавлен 12.02.2013

  • Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

    дипломная работа [2,4 M], добавлен 20.11.2010

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

    курсовая работа [1,5 M], добавлен 19.01.2016

  • Составление программы для расчета начального базиса сбалансированной транспортной задачи, где суммарные запасы поставщиков равны суммарным запросам потребителей. Алгоритм метода потенциалов. Пример решения транспортной задачи методом наименьшей стоимости.

    отчет по практике [991,3 K], добавлен 06.12.2013

  • Условия математической транспортной задачи для ее решения методом потенциалов. Опорный план и проверка целевой функции. Окончательный вариант плана поставок товара предоставленный программой "АОС транспортная задача". Стоимость доставки единицы груза.

    лабораторная работа [1,4 M], добавлен 15.10.2015

  • Сущность и постановка транспортной задачи для n переменных, их виды, применение и пример решения в MS Excel. Управляющие структуры ветвления Maple языка (if предложение). Решение транспортной задачи в векторных координатах для двух и трёх матриц.

    дипломная работа [109,3 K], добавлен 12.01.2011

  • Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

    контрольная работа [118,5 K], добавлен 11.04.2012

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

    контрольная работа [117,9 K], добавлен 08.12.2010

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

    курсовая работа [329,7 K], добавлен 22.01.2016

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.