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

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

«Транспортные задачи»

Содержание

Введение

Глава 1. Обзор теоретических сведений по теме: «Решение транспортной задачи»

1.1 Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей

1.2 Метод потенциалов

1.3 Определение оптимального и опорного плана транспортной задачи

1.4 Понятие потенциала и цикла

Вывод по главе 1

Глава 2. Решение транспортной задачи

2.1 Построение математической модели

2.2 Решение задачи

2.3 Решение транспортной задачи при помощи табличного редактора Excel

Заключение

Список литературы

Введение

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

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

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

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

Для реализации данной темы необходимо:

1. изучить теоретический материал,

2. применить теоретические навыки при решении конкретной задачи,

3. рассмотреть решение той же задачи в табличном редакторе Excel.

транспортный задача опорный редактор

Глава 1. Обзор теоретических сведений по теме: «Решение транспортной задачи»

1.1 Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей

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

Пусть имеется m пунктов производства некоего однородного продукта А₁…,А_i…,A_m и n пунктов его потребления B₁…,B_j…,B_n. В пункте А_i (i=1,2,3,…,m) производится А_i единиц, а в пункте B_j (j=1,2,3,…,n) потребляется B_j единиц продукта.

Предполагается, что

Транспортные издержки, связанные с перевозкой единицы продукта из пункта A_i в пункт B_j равны C_ij.

Суть задачи состоит в составлении оптимального плана перевозок, минимизирующего суммарные транспортные издержки, при реализации которого запросы всех пунктов потребления B_j j=1,2,3,…,n, были бы удовлетворены за счет производство продукта в пунктах А_i i=1,2,3,…,m.

Пусть x_ij- количество продукта, перевозимого из пункта A_i в пункт B_j. Тогда транспортная задача формулируется так: определить значения переменных x_ij, i=1,2,3,…,m, j=1,2,3,…,n, минимизирующих транспортные издержки.

c_ijx_ij

при условиях,

(1)

(2)

, i=1,2,…,m; j=1,2,…,n.(3)

Множество , i=1,2,…,m; j=1,2,…,n., удовлетворяющее этим условиям, называется планом перевозок, а его элементы - перевозками.

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

1. Задача надежности изделий.

2. Задача замены оборудования.

3. Теория расписаний (так называемая теория календарного планирования).

4. Задача распределения ресурсов.

5. Задача ценообразования.

6. Теория сетевого планирования.

В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с m баз A₁, A₂,…,A_m, n потребителям B₁, B₂,…,B_n.

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

Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно A₁, A₂,…,A_m, а общее количество имеющегося в наличии груза-A:

A= A₁+ A₂+…+A_m; (1.1)

заказы каждого из потребителей (потребности) обозначим соответственно B₁, B₂,…,B_n, а общее количество потребностей - B:

B= B₁+ B₂+…+B_n; (1.2)

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

a=b; (1.3)

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

ab; (1.3)

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

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

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

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

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

Условие a=b или ab означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи.

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

(2.1)

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

Такая структура системы (2.1) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием i2, j2.Перепишем систему (2.1) в виде,

(2.1)

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

При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь i2, j2).

В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные x₁₂,x₁₃,…,x_1n с помощью вертикальных уравнений, мы получаем уравнение

или иначе

(2.2)

где символ означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные x₂₁,x₃₁,…,x_m1 с помощью горизонтальных уравнений, мы получаем уравнение (2.2')

Так как для закрытой модели транспортной задачи a=b, то полученные нами уравнения (2.2) и (2.2') одинаковы и, исключив из одного из них неизвестное x₁₁, мы получим уравнение-тождество 0=0, которое из системы вычеркивается.

Итак, преобразование системы (2.1) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (2.2). Остальные уравнения остаются неизменными. Система приняла вид (2.3)

В системе (2.3) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного x₁₁ [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется m+n-1 уравнений, выделенный базис содержит m+n-1 неизвестных, а, следовательно, и ранг системы (2.1) r=m+n-1.

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

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

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

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

Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).

Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен m+n-1 то среди всех mn неизвестных выделяется m+n-1 базисных неизвестных, а остальные (m-n)*(n-1) неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем m+n-1 заполненных и (m-n)*(n-1) пустых клеток.

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

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

Замечание 2. Под величинами C_ij, очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, x_ij выражены в тоннах, а C_ij в километрах, то величина S, определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.

1.2 Метод потенциалов

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

1.3 Определение оптимального и опорного плана транспортной задачи

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

Число переменных Xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах равно n+m. Так как мы предполагаем, что выполняется условие

, то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше - то выраженным. Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля.

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

Для определения оптимального плана транспортной задачи можно

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

1.4 Понятие потенциала и цикла

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

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

1. Одно из неизвестных последовательности свободное, а все остальные - базисные.

2. Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.

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

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

Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

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

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

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

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

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

Вывод по главе 1

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

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

Цикл - это последовательность клеток таблицы транспортной задачи (i₁,j₁), (i₁,j₂), (i₂,j₂), … , (i_k,j₁), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Рассмотрен алгоритм решения транспортной задачи методом потенциалов:

1. Проверяют выполнение необходимого и достаточного условия разрешимости задачи.

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

3. Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений u_i +v_j =c_ij при x_ij >0. Для того чтобы найти частное решение системы, одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задаю произвольно некоторое значение (чаще нуль).

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

Кратко и ясно описывается применение транспортной задачи для решения экономических задач простым способом.

Глава 2. Решение транспортной задачи

2.1 Построение математической модели

Введем переменные задачи (матрицу перевозок)

		Х11	Х12	Х13	Х14	X15
X=		Х21	Х22	Х23	Х24	X25
		Х31	Х32	Х33	Х34	X35

Матрица реализации золота:

	7	9	15	4	18
С=	13	25	8	15	5
	5	11	6	20	12

Целевая функция равна:

Z(x)= 7х11 + 9х12 + 15х13 + 4х14 + 18x5 + 13х21 + 25х22 + 8х23 + 15х24 +5x25 + 5х31 + + 11х32 + 6х33 + 20х34 + 12x35

Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам 1-му месторождению, а сумма перевозок во второй строке матрицы X-запасам 2-го месторождения, и сумма перевозок в третьей строке матрицы X-запасам 3-го месторождения:

х11+х12+х13+х14+x15=200

х21+х22+х23+х24+x25=250

х31+х32+х33+х34+x35=250

Это означает, что запасы месторождения вывозятся полностью.

Суммы перевозок золота, стоящих в каждом столбце матрицы X, должны быть равны запросам городов:

х11+х21+х31=80

х12+х22+х32=260

х13+х23+х33=100

х14+х24+х34=140

x15+x25+x35=120

Это означает, что запросы городов удовлетворяются полностью.

Необходимо также учитывать, что перевозки не могут быть отрицательными:

x_ji?0, i=1,2,3 j=1,2,3,4

Следовательно, математическая модель рассматриваемой задачи имеет вид:

Z(x)= 7х11 + 9х12 + 15х13 + 4х14 + 18x5 + 13х21 + 25х22 + 8х23 + 15х24 +5x25 + 5х31 + + 11х32 + 6х33 + 20х34 + 12x35>min

х11+х12+х13+х14+x15=200

х21+х22+х23+х24+x25=250

х31+х32+х33+х34+x35=250

х11+х21+х31=80

х12+х22+х32=260

х13+х23+х33=100

х14+х24+х34=140

x15+x25+x35=120

и условия неотрицательности x_ji?0, i=1,2,3 j=1,2,3,4,5

2.2 Решение задачи. Транспортная задача

Математическая модель транспортной задачи:

F = ??c_ijx_ij, (1)

при условиях:

?x_ij = a_i, i = 1,2,…, m, (2)

?x_ij = b_j, j = 1,2,…, n, (3)

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

	1	2	3	4	5	Запасы
1	7	9	15	4	18	200
2	13	25	8	15	5	250
3	5	11	6	20	12	250
Потребности	80	260	100	140	120

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 200 + 250 + 250 = 700

?b = 80 + 260 + 100 + 140 + 120 = 700

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	7	9	15	4	18	200
2	13	25	8	15	5	250
3	5	11	6	20	12	250
Потребности	80	260	100	140	120

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	1	2	3	4	5	Запасы
1	7	9[60]	15	4[140]	18	200
2	13	25[130]	8	15	5[120]	250
3	5[80]	11[70]	6[100]	20	12	250
Потребности	80	260	100	140	120

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=3	v2=9	v3=4	v4=4	v5=-11
u1=0	7	9[60]	15	4[140]	18
u2=16	13	25[130]	8	15	5[120]
u3=2	5[80]	11[70]	6[100]	20	12

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (2;3): 8

Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	7	9[60]	15	4[140]	18	200
2	13	25[130][-]	8[+]	15	5[120]	250
3	5[80]	11[70][+]	6[100][-]	20	12	250
Потребности	80	260	100	140	120

Цикл приведен в таблице (2,3; 2,2; 3,2; 3,3; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	7	9[60]	15	4[140]	18	200
2	13	25[30]	8[100]	15	5[120]	250
3	5[80]	11[170]	6	20	12	250
Потребности	80	260	100	140	120

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=3	v2=9	v3=-8	v4=4	v5=-11
u1=0	7	9[60]	15	4[140]	18
u2=16	13	25[30]	8[100]	15	5[120]
u3=2	5[80]	11[170]	6	20	12

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (2;1): 13

Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	7	9[60]	15	4[140]	18	200
2	13[+]	25[30][-]	8[100]	15	5[120]	250
3	5[80][-]	11[170][+]	6	20	12	250
Потребности	80	260	100	140	120

Цикл приведен в таблице (2,1; 2,2; 3,2; 3,1; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	Запасы
1	7	9[60]	15	4[140]	18	200
2	13[30]	25	8[100]	15	5[120]	250
3	5[50]	11[200]	6	20	12	250
Потребности	80	260	100	140	120

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=3	v2=9	v3=-2	v4=4	v5=-5
u1=0	7	9[60]	15	4[140]	18
u2=10	13[30]	25	8[100]	15	5[120]
u3=2	5[50]	11[200]	6	20	12

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 9*60 + 4*140 + 13*30 + 8*100 + 5*120 + 5*50 + 11*200 = 5340

2.3 Решение транспортной задачи при помощи табличного редактора Excel

Заключение

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

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

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

Список литературы

1 Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры: 9- е изд., перераб. М.: Физматлит,2011. 376 с.

2 Ефимов П.В. Краткий курс аналитической геометрии: Учебник. 13-е изд., стереотип. М.: Физ-матлит,2003.240с.

3 Бермаит А.Ф., Арамаиович И.Г. Краткий курс математического анализа: Учебник. 10-е изд., стереотип. СПб.: "Лань", 2012. 736 с.

4 Пискунов П.С. Дифференциальное и интегральное счисления: Учеб. пособие для втузов. В 2 т. М.: Иитеграл-Пресс, 2004. Т. 1: 416 с; Т. 2:544 с.

5 Щипачев B.C. Основы высшей математики. 4-е изд., стереотип. М.: Высш. шк., 2001.479 с.

6 Демидович Б.П., Кудрявцев В.А. Краткий курс высшей математики: Учеб. пособие для вузов. М.: Астрель,2011.656с.

7 Фихтенгольц Г.М. Основы математического анализа. В 2 т. 7-е изд. М.: Физматлит, 2002. Т. 1: 416 с; Т. 2: 440 с.

8 Матвеев П.М. Методы интегрирования обыкновенных дифференциальных уравнений: Учеб. пособие. 5-е изд., доп. СПб.: "Лань", 2010. 832 с.

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

...