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

ФКОУ СПО «НТТИ» Минздравсоцразвития России

Специальность 230105 «Программное обеспечение вычислительной техники и вычислительных систем»

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

Тема: Транспортная задача. Метод потенциалов

Выполнил студент 3 курса группы 3 сп. пр

(Ф.И.О.)

Руководитель проекта

Консультант проекта

К защите Защита принята с оценкой

2011-2012



Оглавление

• Введение
• 1. Общая часть
• 1.1 Общая постановка транспортной задачи
• 2. Методы построения начального опорного решения
• 2.1 Метод вычеркивания
• 2.2 Метод северо-западного угла
• 2.3 Метод минимальной стоимости
• 3. Метод построения оптимального решения
• 3.1 Метод потенциалов
• 4. Алгоритм решения транспортных задач методом потенциалов
• 5. Специальная часть
• 5.1 Постановка задачи
• 5.2 Решение. Метод минимальной стоимости
• 5.3 Решение. Метод потенциалов
• 6. Расчет задачи в MS Excel
• 6.1 Исследование модели
• Заключение
• Список использованной литературы


Введение

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

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

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

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

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

· задача об оптимальном использовании ресурсов при производственном планировании;

· задача о смесях (планирование состава продукции);

· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

· транспортные задачи (анализ размещения предприятия, перемещение грузов).

Одной из задач линейного программирования является транспортная задача- задача составления оптимального плана перевозок, позволяющего минимизировать суммарный километраж. Транспортная задача, как и задача линейного программирования была впервые поставлена советским экономистом А.Н.Толстым в 1930 году. Разработка общих методов решения задачи линейного программирования и их математическое исследование связано с именем советского ученого Л.В. Канторовича. В 1939 году методам решения задачи линейного программирования посвящено также большое число работ зарубежных ученых. Основной метод решения задачи линейного программирования - симплекс метод - был опубликован в 1949 году Дандигом. Симплекс метод дает решение любой задачи линейного программирования, но если переменных очень много, то решение весьма затруднительно и для более сложных задач симплекс метод стали модифицировать.

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

транспортный моделирование план перевозка



1. Общая часть

1.1 Общая постановка транспортной задачи

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

Рассмотрим постановку таких задач.

Пусть имеем m предприятий A1, A2,..., Am, производящих один и тот же продукт в количествах соответственно a1, a2,..., am.

Пусть, далее, имеется n потребителей (складов) B1, B2,..., Bn с потребностями (вместимостями) соответственно b1, b2,..., bn.

Пусть весь произведенный продукт может быть размещен на складах B1, B2,..., Bn при полном их заполнении.

Пусть, наконец, перевозка единицы продукции из пункта Ai в пункт Bj оценивается величиной cij (cij - заданы).

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

Строим математическую модель.

Пусть xij - количество продукта, перевозимого из пункта Ai в пункт Bj. Из постановки задачи очевидно, что каждый склад вмещает:

А так как производится столько продукции, сколько ее потребляется (складируется), то:



(продукт с предприятия вывозится полностью).

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

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

Таким образом, имеем следующую математическую постановку задачи. Найти такие x_ij, которые доставляют минимум линейной форме L, т.е. и удовлетворяют условиям:

	(1)
	(2)
	(3)

Из (1) и (2) следует, что



Закрытая транспортная задача.

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

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

Однородный груз сосредоточен у т поставщиков в объемах .

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

Известны (i=1,2,…,m; j=1,2,…,n)- стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны.

Исходные данные транспортной задачи записываются в таблице вида

Таблица 1

			…
			…
			…
…	…	…	…	…
			…

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



перевозок

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

(1.1)

i=1,2,…,m, (1.2)

j=1,2,…,n, (1.3)

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

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

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

i=1,2,…,m; j=1,2,…,n,

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

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

.

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

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



2. Методы построения начального опорного решения

Опорное решение транспортной задачи

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

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

Теорема

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

2.1 Метод вычеркивания

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

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

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

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

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

Примеры "вычеркнутого" (опорного) и "не вычеркнутого" (не опорного решений):

Логика вычеркивания:

1. Вычеркнуть все столбцы, в которых всего одна занятая клетка (5 0 0), (0 9 0)

2. Вычеркнуть все строки, в которых всего одна занятая клетка (0 15), (2 0)

3. Повторить цикл (7) (1)

2.2 Метод северо-западного угла

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

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

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

2.3 Метод минимальной стоимости

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(cij).

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

,

заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы груза использованы полностью.

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

На каждом шаге исключается либо один поставщик, либо один потребитель.

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



3.Метод построения оптимального решения

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

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

Общая схема отдельной итерации такова.

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

Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи.

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

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

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

Для свободных клеток транспортной таблицы вычисляются величины



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

Разность потенциалов можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j.

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

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

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины: нечетные -- знаком «+», а четные знаком «--». Знаком «+» отмечаются те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком «--» -- те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «--», выбирается клетка с наименьшим значением.

Она и становится кандидатом на вывод, т. к. уменьшение объема перевозок на большую величину может привести к отрицательным значениям xi,j в других «минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем q, а из объемов клеток, помеченных знаком «--», он вычитается. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описанные выше действия повторяются.

Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке: если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком «--», то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем m + n-1 ненулевых компонент.

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

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

В общем виде модель записывается следующим образом:

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

= c1x1 + c2x2 + ... + cnxn > max(min);

· ограничения:



a11x1 + a12x2 + ... + a1nxn {? = ?} b1, a21x1 + a22x2 + ... + a2nxn {? = ?} b2, ... am1x1 + am2x2 + ... + amnxn {? = ?} bm;	(2.2)

· требование неотрицательности:

xj ? 0,	(2.3)

При этом aij, bi, cj ( ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3).

Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми.

Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

Составить оптимальный план перевозок пищевых продуктов от 4-х поставщиков к 4-м потребителям. Поставщики (П), потребители (М), объёмы вывоза и завоза, кратчайшие расстояния между пунктами вывоза и завоза приведены в таблице.

Поставщики	Потребители	Объёмы вывоза, т
	М1	М2	М3	М4
П1	20	30	25	70	300
П2	5	10	5	65	365
П3	186	215	210	246	149
П4	45	50	45	25	132
Объёмы завоза, т	192	184	80	112



4. Алгоритм решения транспортных задач методом потенциалов

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

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

Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений:

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

если известен потенциал , и

если известен потенциал

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

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

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

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

.

Клетка со знаком «-», в которой достигается



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

.

Далее перейти к пункту 3 данного алгоритма.



5. Специальная часть

5.1 Постановка задачи

Составить оптимальный план перевозок пищевых продуктов от 4-х поставщиков к 4-м потребителям. Поставщики (П), потребители (М), объёмы вывоза и завоза, кратчайшие расстояния между пунктами вывоза и завоза приведены в таблице.

Поставщики	Потребители	Объёмы вывоза, т
	М1	М2	М3	М4
П1	20	30	25	70	300
П2	5	10	5	65	365
П3	186	215	210	246	149
П4	45	50	45	25	132
Объёмы завоза, т	192	184	80	112

5.2 Решение. Метод минимальной стоимости

Поставщики	Потребители	Объёмы вывоза
	Потребитель 1	Потребитель 2	Потребитель 3	Потребитель 4	Потребитель 5
Поставщик 1		20		30		25		70	0	300
			91						209
Поставщик 2		5		10		5		65	0	365
	192		93		80
Поставщик 3		186		215		210		246	0	149
									149
Поставщик 4		45		50		45		25	0	132
							112		20
Объёмы завоза, Т	192		184		80		112		378

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

S₀ = 30 * 91 + 0 * 209 + 5 * 192 + 10 * 93 + 5 * 80 + 0 * 149 + 25 * 112 + 0 * 20 = 7820 ден. ед.

5.3 Решение. Метод потенциалов

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij - тариф клетки AiBj)

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

Примем v5 = 0.
v5 + u1 = c15	v5 + u1 = 0
v5 + u3 = c35	v5 + u3 = 0
v5 + u4 = c45	v5 + u4 = 0
v2 + u1 = c12	v2 + u1 = 30
v2 + u2 = c22	v2 + u2 = 10
v3 + u2 = c23	v3 + u2 = 5
v4 + u4 = c44	v4 + u4 = 25
v1 + u2 = c21	v1 + u2 = 5

u₁ = 0 - 0 = 0; v₄ = 25 - 0 = 25;

u₃ = 0 - 0 = 0; v₁ = 5 - ( -20 ) = 25.

u₄ = 0 - 0 = 0; u₂ = 10 - 30 = -20;

v₂ = 30 - 0 = 30;

Поставщик	Потребитель	U j
	B 1	B 2	B 3	B 4	B 5
A 1	20	91 30	25	70	209 0	u 1 = 0
A 2	192 5	93 10	80 5	65	0	u 2 = -20
A 3	186	215	210	246	149 0	u 3 = 0
A 4	- 45	- 50	- 45	112 25	20 0	u 4 = 0
V i	v 1 = 25	v 2 = 30	v 3 = 25	v 4 = 25	v 5 = 0

₁₁ = c₁₁ - ( u₁ + v₁ ) = 20 - ( 0 + 25 ) = -5

₁₃ = c₁₃ - ( u₁ + v₃ ) = 25 - ( 0 + 25 ) = 0

₁₄ = c₁₄ - ( u₁ + v₄ ) = 70 - ( 0 + 25 ) = 45

₂₄ = c₂₄ - ( u₂ + v₄ ) = 65 - ( -20 + 25 ) = 60

₂₅ = c₂₅ - ( u₂ + v₅ ) = 0 - ( -20 + 0 ) = 20

₃₁ = c₃₁ - ( u₃ + v₁ ) = 186 - ( 0 + 25 ) = 161

₃₂ = c₃₂ - ( u₃ + v₂ ) = 215 - ( 0 + 30 ) = 185

₃₃ = c₃₃ - ( u₃ + v₃ ) = 210 - ( 0 + 25 ) = 185

₃₄ = c₃₄ - ( u₃ + v₄ ) = 246 - ( 0 + 25 ) = 221

₄₁ = c₄₁ - ( u₄ + v₁ ) = 45 - ( 0 + 25 ) = 20

₄₂ = c₄₂ - ( u₄ + v₂ ) = 50 - ( 0 + 30 ) = 20

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

= c₄₃ - ( u₄ + v₃ ) = 45 - ( 0 + 25 ) = 20

Оценка свободной ячейки A₁B₁ отрицательная (₁₁ =-5) , следовательно, решение не является оптимальным.

Построим цикл для выбранной ячейки A₁B₁

A1B1 , A1B2 , A2B2 , A2B1 Ячейки образующие цикл для свободной ячейки A1B1 :



Поставщик	Потребитель	U j
	B 1	B 2	B 3	B 4	B 5
A 1	-5 20	91 30	0 25	45 70	209 0	u 1 = 0
A 2	192 5	93 10	80 5	60 65	20 0	u 2 = -20
A 3	161 186	185 215	185 210	221 246	149 0	u 3 = 0
A 4	20 45	20 50	20 45	112 25	20 0	u 4 = 0
V i	v 1 = 25	v 2 = 30	v 3 = 25	v 4 = 25	v 5 = 0

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

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4	B 5
A 1	-5 20	91 30	25	70	209 0	300
A 2	192 5	93 10	80 5	65	0	365
A 3	186	215	210	246	149 0	149
A 4	45	50	45	112 25	20 0	132
Потребность	192	184	80	112	378

Среди ячеек цикла A1B2 , A2B1 , номера которых четные, найдем ячейку, обладающую наименьшим значением.

min = { 91, 192 } = 91

В данном случае, это ячейка A1B2

Поставщик	Потребитель	Запас
	B 1	B 2	B 3	B 4	B 5
A 1	+ 91 -5 20	91 - 91 30	25	70	209 0	300
A 2	192 - 91 5	93 + 91 10	80 5	65	0	365
A 3	186	215	210	246	149 0	149
A 4	45	50	45	112 25	20 0	132
Потребность	192	184	80	112	378

20 * 91 - 30 * 91 + 10 * 91 - 5 * 91 = ( 20 - 30 + 10 - 5 ) * 91 = -5 * 91 ден. ед.

Общие затраты на доставку всей продукции, для данного решения, составляют

S₀ = 7820 + ( - 455 ) = 7365 ден. ед.

Ячейка A₁B₂ выйдет из базиса, мы перестали доставлять продукцию от поставщика A₁ к потребителю B₂

Ячейка A₁B₁ станет базисной, мы ввели новый маршрут доставки продукции от поставщика A₁ к потребителю B₁

Для базисной ячейки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута. (u_i + v_j = c_ij, где c_ij - тариф клетки A_i B_j) Поскольку, число базисных клеток - 8, а общее количество потенциалов равно 9, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v5 = 0.
v5 + u1 = c15	v5 + u1 = 0	u1 = 0 - 0 = 0
v5 + u3 = c35	v5 + u3 = 0	u3 = 0 - 0 = 0
v5 + u4 = c45	v5 + u4 = 0	u4 = 0 - 0 = 0
v1 + u1 = c11	v1 + u1 = 20	v1 = 20 - 0 = 20
v1 + u2 = c21	v1 + u2 = 5	u2 = 5 - 20 = -15
v2 + u2 = c22	v2 + u2 = 10	v2 = 10 - ( -15 ) = 25
v3 + u2 = c23	v3 + u2 = 5	v3 = 5 - ( -15 ) = 20
v4 + u4 = c44	v4 + u4 = 25	v4 = 25 - 0 = 25

Поставщик	Потребитель	U j
	B 1	B 2	B 3	B 4	B 5
A 1	91 20	30	25	70	209 0	u 1 = 0
A 2	101 5	184 10	80 5	65	0	u 2 = -15
A 3	186	215	210	246	149 0	u 3 = 0
A 4	45	50	45	112 25	20 0	u 4 = 0
V i	v 1 = 20	v 2 = 25	v 3 = 20	v 4 = 25	v 5 = 0

Найдем оценки свободных ячеек следующим образом:

12 = c12 - ( u1 + v2 ) = 30 - ( 0 + 25 ) = 5
13 = c13 - ( u1 + v3 ) = 25 - ( 0 + 20 ) = 5
14 = c14 - ( u1 + v4 ) = 70 - ( 0 + 25 ) = 45
24 = c24 - ( u2 + v4 ) = 65 - ( -15 + 25 ) = 55
25 = c25 - ( u2 + v5 ) = 0 - ( -15 + 0 ) = 15
31 = c31 - ( u3 + v1 ) = 186 - ( 0 + 20 ) = 166
32 = c32 - ( u3 + v2 ) = 215 - ( 0 + 25 ) = 190
33 = c33 - ( u3 + v3 ) = 210 - ( 0 + 20 ) = 190
34 = c34 - ( u3 + v4 ) = 246 - ( 0 + 25 ) = 221
41 = c41 - ( u4 + v1 ) = 45 - ( 0 + 20 ) = 25
42 = c42 - ( u4 + v2 ) = 50 - ( 0 + 25 ) = 25
43 = c43 - ( u4 + v3 ) = 45 - ( 0 + 20 ) = 25

Поставщик	Потребитель	U j
	B 1	B 2	B 3	B 4	B 5
A 1	91 20	- 5 30	- 5 25	- 45 70	209 0	u 1 = 0
A 2	101 5	184 10	80 5	- 55 65	- 15 0	u 2 = -15
A 3	- 166 186	- 190 215	- 190 210	- 221 246	149 0	u 3 = 0
A 4	- 25 45	- 25 50	- 25 45	112 25	20 0	u 4 = 0
V i	v 1 = 20	v 2 = 25	v 3 = 20	v 4 = 25	v 5 = 0

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

Smin = 20 * 91+0 * 209+5 * 101+10 * 184+5 * 80+0 * 149+25 * 112+0 * 20 = 7365

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



6. Расчет задачи в MS Excel

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

2. В таблице План доставки продублировал столбец «Объёмы вывоза» и столбец «Объёмы завоза», а так же добавлены:

· столбец «Использовано»

· строка «Объём доставки»

· ячейка «Общие суммы»

3. Заполнил таблицу «План доставки» формулами необходимыми для создания ограничений:

· Ограничения на запасы - в ячейку G13 столбца «Использовано» ввел =СУММ(B13:F13);

· Ограничения на потребности - в ячейку B17 строки «Объём доставки» ввел =СУММ(B13:B16).

4. Записал общие суммы по столбцам и строкам:

· В ячейку H17 столбца «Объёмы вывоза» ввел =СУММ(H13:H16);

· В ячейку G18 строки «Объёмы завоза» ввел =СУММ(B18:F18);

· В ячейку H18 ввел логическую формулу для контроля общих сумм =ЕСЛИ(H17=G18;"Совпадает";"не совпадает");

5. В ячейку H19 записал формулу для ЦФ =СУММПРОИЗВ(B4:F7;B13:F16)

6.1 Исследование модели

Для поиска оптимального набора значений параметров плана доставки, который соответствует минимальному значению ЦФ (общей стоимости всех перевозок), Я воспользовался надстройкой Поиск решения.



В окне параметры поиска решения активизировал флажки Линейная модель и Неотрицательные значения. Нажав кнопку Выполнить получил результат.

Структура сценария
		Текущие значения:	закрытая м
Изменяемые:
	$B$13	91	91
	$C$13	0	0
	$D$13	0	0
	$E$13	0	0
	$F$13	209	209
	$B$14	101	101
	$C$14	184	184
	$D$14	80	80
	$E$14	0	0
	$F$14	0	0
	$B$15	0	0
	$C$15	0	0
	$D$15	0	0
	$E$15	0	0
	$F$15	149	149
	$B$16	0	0
	$C$16	0	0
	$D$16	0	0
	$E$16	112	112
	$F$16	20	20
Результат:
	$G$13	300	300
	$B$17	192	192
	$H$19	7365	7365

Отчет по пределам:





Заключение

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



Список использованной литературы

1. А.В.Кузнецов, Г.И.Новикова, И.И.Холод - «Сборник задач по математическому программированию». Минск, Высшая школа, 1985г.

2. Экономико-математическое моделирование. Учеб. для ВУЗов / Под ред. А.Д. Дрогобыцкого. - М.: Экзамен, 2004.

3. Карпелович Ф.И., Садовский Л.Е. Элементы линейной алгебры и линейного программирования. - М.: Физматгиз, 1963.

4. Нестеров Е.П. Транспортные задачи линейного программирования. - М.: Транспорт, 1971.

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