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

НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ЭКОНОМИКО-КОМПЬЮТЕРНЫЙ ТЕХНИКУМ»

ГРАФИЧЕСКАЯ КУРСОВАЯ РАБОТА
по дисциплине: «Математические методы»
на тему: "Транспортная задача"

Выполнил:
студент 4-го курса группы 08-1 (п)
Лагутин Р.И.
Руководитель: ХодаковскаяТ.Ю.
Курск – 2010 г.
Задание
Цели работы: изучить методы решения транспортной задачии их реализацию при решении практической задачи.
Задания:
1. Рассмотреть понятие транспортной задачи, ее типы.
2. Рассмотреть различные методы решения транспортной задачи.
3. Построить первый опорный план данной транспортной задачи двумя различнымиметодами.
4. Найти оптимальный план перевозок данной задачи методом потенциалов.
5. Решить данную задачу с использованием MS Excel (привести описание решения).
6. Составьте компьютерную программу по решению задач данного типа (привестиописание программы, приложить программу в электронном виде).
Вариант 4.1.
На четырех складах фирмы находится 70, 30, 40 и 60 холодильниковсоответственно, которые следует доставить в четыре магазина фирмы в количестве 50,70, 40 и 40 холодильников в каждый из магазинов. Стоимости перевозки одного холодильникас первого склада в каждый из магазинов составляют 6, 4, 9 и 7 денежных единиц соответственно,со второго склада — 7, 2, 5 и 6 денежных единиц, с третьего склада — 2, 6, 3 и 3денежных единиц, с четвертого склада — 3, 3, 6 и 5 денежных единиц соответственно.Определить план перевозок холодильников со складов в магазины, при котором общиезатраты на перевозку были бы наименьшими.

Оглавление
 
Задание
Введение
Транспортная задача
Математическая модель
Опорный план
Распределительный метод оптимального плана
Решение транспортной задачи методом потенциалов
Всякий потенциальный план является оптимальным
Заключение
Список используемой литературы
 
Введение
Каждый человек ежедневно, не всегда осознавая это, решает проблему:как получить наибольший эффект, обладая ограниченными средствами. Наши средстваи ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было нетак. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника.Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план,или программу действий. Раньше план в таких случаях составлялся “на глазок”. В серединеXX века был создан специальный математический аппарат, помогающий это делать “понауке”. Соответствующий раздел математики называется математическим программированием.Слово “программирование" здесь и в аналогичных терминах (“линейное программирование,динамическое программирование” и т.п.) обязано отчасти историческому недоразумению,отчасти неточному переводу с английского. По-русски лучше было бы употребить слово“планирование”. С программированием для ЭВМ математическое программирование имеетлишь то общее, что большинство возникающих на практике задач математического программированияслишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительносоставив программу. Временем рождения линейного программирования принято считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математическиеметоды организации и планирования производства”.
Под названием “транспортная задача” объединяется широкий кругзадач с единой математической моделью. Данные задачи относятся к задачам линейногопрограммирования и могут быть решены симплексным методом. Однако матрица системыограничений транспортной задачи настолько своеобразна, что для ее решения разработаныспециальные методы. Эти методы, как и симплексный метод, позволяют найти начальноеопорное решение, а затем, улучшая его, получить оптимальное решение.
Целью транспортной задачи является обеспечение получения(доставки) продукции (товара) потребителю в нужное время и место при минимальновозможных совокупных затратах трудовых, материальных, финансовых ресурсов.
Цель транспортной деятельности считается достигнутой привыполнении шести условий:
1. нужный товар;
2. необходимого качества;
3. в необходимом количестве доставлен;
4. в нужное время;
5. в нужное место;
6. с минимальными затратами.
Объектом изучения являются материальные и соответствующиеим финансовые, информационные потоки, сопровождающие производственно-коммерческуюдеятельность.
В данной курсовой работе будут рассмотрены понятие транспортнойзадачи, ее типы, различные методы решения. Решена задача по заданию 4.1 с помощьюMS Excel и приложена компьютерная программа по решению задачи данноготипа.
Транспортная задача
Линейные транспортные задачи составляют особый класс задач линейногопрограммирования. Задача заключается в отыскании такого плана перевозок продукциис m складов в пункт назначения n который, потребовал бы минимальныхзатрат. Если потребитель j получает единицу продукции (по прямой дороге)со склада i, то возникают издержки Сij. Предполагается,что транспортные расходы пропорциональны перевозимому количеству продукции, т.е.перевозка k единиц продукции вызывает расходы k С ij.
Далее,
 
/>
где ai есть количество продукции, находящеесяна складе i , и bj — потребность потребителя j.
Замечание.
1. Если сумма запасов в пунктах отправления превышает сумму поданныхзаявок />то количество продукции,равное /> остается на складах.В этом случае мы введем «фиктивного» потребителя n +1 с потребностью/> и положим транспортныерасходы pi,n +1 равными 0 для всех i.
2. Если сумма поданных заявок превышает наличные запасы /> то потребностьне может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильнымбалансом, если ввести фиктивный пункт отправления m + 1 с запасом /> и стоимость перевозокиз фиктивного пункта отправления во все пункты назначения принять равным нулю.
 Математическая модель
 
/>
/>
/>
/>
/>
где xij количество продукции, поставляемоесо склада i потребителю j, а С ij издержки(стоимость перевозок со склада i потребителю j).
 Опорный план
Решение транспортной задачи начинается с нахождения опорногоплана. Для этого существуют различные способы. Например, способ северо-западногоугла, способ минимальной стоимости по строке, способ минимальной стоимости по столбцуи способ минимальной стоимости таблицы. Рассмотрим простейший, так называемый способсеверо-западного угла. Пояснить его проще всего будет на конкретном примере:
Условия транспортной задачи заданы транспортной таблицей.

Таблица № 1
ПН
ПО
В1
В2
В3
В4
В5
Запасы
аi
А1 10 8 5 6 9 48
А2 6 7 8 6 5 30
А3 8 7 10 8 7 27
А4 7 5 4 6 8 20
Заявки
bj 18 27 42 12 26 125
Будем заполнять таблицу перевозками постепенно начиная с левойверхней ячейки («северо-западного угла» таблицы). Будем рассуждать приэтом следующим образом. Пункт В1 подал заявку на 18 единиц груза.Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте А1,и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В1удовлетворена, а в пункте А1 осталось ещё 30 единиц груза. Удовлетворимза счёт них заявку пункта В2 (27 единиц), запишем 27 в клетке(1,2); оставшиеся 3 единицы пункта А1 назначим пункту В3.В составе заявки пункта В3 остались неудовлетворёнными 39 единиц.Из них 30 покроем за счёт пункта А2, чем его запас будет исчерпан,и ещё 9 возьмём из пункта А3. Из оставшихся 18 единиц пункта А312 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5,что вместе со всеми 20 единицами пункта А4 покроет его заявку.На этом распределение запасов закончено; каждый пункт назначения получил груз, согласносвоей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующемузапасу, а в столбце — заявке.
Таким образом, нами сразу же составлен план перевозок, удовлетворяющийбалансовым условиям. Полученное решение является опорным решением транспортной задачи:
 

Таблица № 2
ПН
ПО
В1
В2
В3
В4
В5
Запасы
аi
А1
10
18
8
27
5
3 6 9 48
А2 6 7
8
30 6 5 30
А3 8 7
10
9
8
12
7
6 27
А4 7 5 4 6
8
20 20
Заявки
bj 18 27 42 12 26 125
Составленный нами план перевозок, не является оптимальным постоимости, так как при его построении мы совсем не учитывали стоимость перевозокСij.
Другой способ — способ минимальной стоимости по строке — основанна том, что мы распределяем продукцию от пункта Ai не в любойиз пунктов Bj, а в тот, к которому стоимость перевозки минимальна.Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетови находим минимальную стоимость перевозки из оставшихся пунктов Bj. Вовсем остальном этот метод схож с методом северо-западного угла. В результате, опорныйплан, составленный способом минимальной стоимости по строке выглядит, так как показанов таблице № 3. При этом методе может получиться, что стоимости перевозок Cijи Cik от пункта Ai к пунктам Bj
и Bk равны. В этом случае, с экономическойточки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше.Так, например, в строке 2: C21 = C24, но заявкаb1 больше заявки b4, поэтому 4 единицы продукциимы распределим в клетку (2,1).

Таблица № 3
ПН
ПО
В1
В2
В3
В4
В5
Запасы
аi
А1 10 8
5
42
6
6 9 48
А2
6
4 7 8 6
5
26 30
А3 8
7
27 10 8
7 27
А4
7
14 5 4
6
6 8 20
Заявки
bj 18 27 42 12 26 125
Способ минимальной стоимости по столбцу аналогичен предыдущемуспособу. Их отличие состоит в том, что во втором способе мы распределяем продукциюот пунктов Bi к пунктам Aj по минимальной стоимостиCji.
Опорный план, составленный способами минимальных стоимостей,обычно более близок к оптимальному решению. Так в нашем примере общие затраты натранспортировку по плану, составленному первым способом F0 = 1039,а по второму F0 = 723. Клетки таблицы, в которых стоят ненулевыеперевозки, являются базисными. Их число должно равняться m + n — 1. Необходимоотметить также, что встречаются такие ситуации, когда количество базисных клетокменьше чем m + n — 1. В этом случае распределительная задача называется вырожденной.И следует в одной из свободных клеток поставить количество перевозок равное нулю.Так, например, в таблице № 3:
 
m + n — 1 = 4 + 5 — 1 = 8,
 
а базисных клеток 7, поэтому нужно в одну из клеток строки 3или столбца 2 поставить значение “0”. Например в клетку (3,5). Составляя план поспособам минимальных стоимостей в отличии от плана по способу северо-западного угламы учитываем стоимости перевозок Cij, но все же не можем утверждать,что составленный нами план является оптимальным.
 Распределительный метод оптимального плана
Теперь попробуем улучшить план, составленный способом северо-западногоугла. Перенесем, например, 18 единиц из клетки (1,1) в клетку (2,1) и чтобы не нарушитьбаланса перенесём те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новыйплан. Подсчитав стоимость опорного плана (она ровняется 1039) и стоимость новогоплана (она ровняется 913) нетрудно убедиться, что стоимость нового плана на 126единиц меньше. Таким образом, за счёт циклической перестановки 18 единиц груза изодних клеток в другие нам удалось понизить стоимость плана:
Таблица №4
ПН
ПО
В1
В2
В3
В4
В5
Запасы
аi
А1 10
8
27
5
21 6 9 48
А2
6
18 7
8
12 6 5 30
А3 8 7
10
9
8
12
7
6 27
А4 7 5 4 6
8
20 20
Заявки
bj 18 27 42 12 26 125
На этом способе уменьшения стоимости в дальнейшем и будет основаналгоритм оптимизации плана перевозок. Циклом в транспортной задаче мы будемназывать несколько занятых клеток, соединённых замкнутой, ломанной линией, котораяв каждой клетке совершает поворот на 90°. Существует несколько вариантов цикла:
1.)                                           2.)                                3.)
/>
/>
/>
Нетрудно убедиться, что каждый цикл имеет чётное число вершини значит, чётное число звеньев (стрелок). Условимся отмечать знаком + тевершины цикла, в которых перевозки необходимо увеличить, а знаком —, те вершины,в которых перевозки необходимо уменьшить. Цикл с отмеченными вершинами будем называтьозначенным. Перенести какое-то количество единиц груза по означенному циклу, этозначит увеличить перевозки, стоящие в положительных вершинах цикла, на это количествоединиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество.Очевидно, при переносе любого числа единиц по циклу равновесие между запасами изаявками не меняется: по прежнему сумма перевозок в каждой строке равна запасамэтой строки, а сумма перевозок в каждом столбце — заявке этого столбца. Таким образом,при любом циклическом переносе, оставляющем перевозки неотрицательными допустимыйплан остаётся допустимым.
Стоимость же плана при этом может меняться: увеличиваться илиуменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении однойединицы груза по означенному циклу. Очевидно, цена цикла ровна алгебраической сумместоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутсясо знаком +, а в отрицательных со знаком —. Обозначим цену цикла через g.
При перемещении одной единицы груза по циклу стоимость перевозокувеличивается на величину g. При перемещении по нему k единиц грузастоимость перевозок увеличиться на kg. Очевидно, для улучшения плана имеетсмысл перемещать перевозки только по тем циклам, цена которых отрицательна. Каждыйраз, когда нам удаётся совершить такое перемещение, стоимость плана уменьшаетсяна соответствующую величину kg. Так как перевозки не могут быть отрицательными,мы будем пользоваться только такими циклами, отрицательные вершины которых лежатв базисных клетках таблицы, где стоят положительные перевозки.
Если циклов с отрицательной ценой в таблице больше не осталось,это означает, что дальнейшее улучшение плана невозможно, то есть оптимальный пландостигнут. Метод последовательного улучшения плана перевозок и состоит в том, чтов таблице отыскиваются циклы с отрицательной ценой, по ним перемещаются перевозки,и план улучшается до тех пор, пока циклов с отрицательной ценой уже не останется.При улучшении плана циклическими переносами, как правило, пользуются приёмом, заимствованнымиз симплекс-метода: при каждом шаге (цикле) заменяют одну свободную переменную набазисную, то есть заполняют одну свободную клетку и взамен того освобождают однуиз базисных клеток. При этом общее число базисных клеток остаётся неизменным и равнымm + n — 1. Этот метод удобен тем, что для него легче находить подходящиециклы. Можно доказать, что для любой свободной клетке транспортной таблице всегдасуществует цикл и притом единственный, одна из вершин которого лежит в этой свободнойклетке, а все остальные в базисных клетках. Если цена такого цикла, с плюсом в свободнойклетке, отрицательна, то план можно улучшить перемещением перевозок по данному циклу.Количество единиц груза k, которое можно переместить, определяется минимальнымзначением перевозок, стоящих в отрицательных вершинах цикла (если переместить большеечисло единиц груза, возникнут отрицательные перевозки).
Применённый выше метод отыскания оптимального решения транспортнойзадачи называется распределённым; он состоит в непосредственном отыскании свободныхклеток с отрицательной ценой цикла и в перемещении перевозок по этому циклу.
Распределительный метод решения транспортной задачи, с которыммы познакомились, обладает одним недостатком: нужно отыскивать циклы для всех свободныхклеток и находить их цены. От этой трудоёмкой работы нас избавляет специальный методрешения транспортной задачи, который называется методом потенциалов.
 Решение транспортной задачи методом потенциалов
Этот метод позволяет автоматически выделять циклы с отрицательнойценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями
/>
/>
/>
/>
/>
Стоимость перевозки единицы груза из Ai в Bjравна C ij; таблица стоимостей задана. Требуется найти план перевозокxij, который удовлетворялбы балансовым условиями при этом стоимость всех перевозок быламинимальна.
Идея метода потенциалов для решения транспортной задачи сводитьсяк следующему. Представим себе что каждый из пунктов отправления Aiвносит за перевозку единицы груза (всё равно куда) какую-то сумму ai;в свою очередь каждый из пунктов назначения Bj также вносит заперевозку груза (куда угодно) сумму bj. Эти платежи передаютсянекоторому третьему лицу (“перевозчику“). Обозначим ai + bj =čij (i=1. m; j=1. n) и будем называть величинуčij “псевдостоимостью" перевозки единицыгруза из Ai в Bj. Заметим, что платежи aiи bj не обязательно должны быть положительными; не исключено,что “перевозчик" сам платит тому или другому пункту какую-то премию за перевозку.
Также надо отметить, что суммарная псевдостоимость любого допустимогоплана перевозок при заданных платежах (ai и bj)одна и та же и от плана к плану не меняется. До сих пор мы никак не связывали платежи(ai и bj) и псевдостоимости čijс истинными стоимостями перевозок C ij. Теперь мы установим междуними связь. Предположим, что план xij невырожденный (число базисныхклеток в таблице перевозок ровно m + n — 1). Для всех этих клеток xij>0. Определим платежи (ai и bj) так,чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:
čij = ai + bj= сij, при xij >0.
Что касается свободных клеток (где xij = 0),то в них соотношение между псевдостоимостями и стоимостями может быть, какое угодно.Оказывается соотношение между псевдостоимостями и стоимостями в свободных клеткахпоказывает, является ли план оптимальным или же он может быть улучшен. Существуетспециальная теорема: Если для всех базисных клеток плана xij >0,ai + bj = čij=сij, а для всех свободных клеток xij=0,ai + bj = čij≤сij, то план является оптимальным и никакимиспособами улучшен быть не может. Нетрудно показать, что это теорема справедливатакже для вырожденного плана, и некоторые из базисных переменных равны нулю. Планобладающий свойством:
čij= сij(для всех базисных клеток) (1)
čij≤ сij(для всех свободных клеток) (2)
называется потенциальным планом, а соответствующие емуплатежи (ai и bj) — потенциалами пунктов Aiи Bj (i=1,.,m; j=1,.,n).
Пользуясь этой терминологией вышеупомянутую теорему можно сформулироватьтак:
 Всякий потенциальный план является оптимальным
Итак, для решения транспортной задачи нам нужно одно — построитьпотенциальный план. Оказывается его можно построить методом последовательных приближений,задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию(1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимостиперевозок в данной клетке; затем, улучшая план следует одновременно менять системуплатежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогаетследующее свойство платежей и псевдостоимостей: какова бы ни была система платежей(ai и bj) удовлетворяющая условию (1), для каждойсвободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостьюв данной клетке: gi,j= сi,j — či,j.
Таким образом, при пользовании методом потенциалов для решениятранспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода:поиски циклов с отрицательной ценой.
Процедура построения потенциального (оптимального) плана состоитв следующем. В качестве первого приближения к оптимальному плану берётся любой допустимыйплан (например, построенный способом минимальной стоимости по строке). В этом планеm + n — 1 базисных клеток, где m — число строк, n — число столбцовтранспортной таблицы. Для этого плана можно определить платежи (aiи bj), так, чтобы в каждой базисной клетке выполнялось условие:ai + bj = сij (3)
Уравнений всего m + n — 1, а число неизвестных равно m+n. Следовательно, одну из этих неизвестных можно задать произвольно (например,равной нулю). После этого из m + n — 1 уравнений можно найти остальные платежиai, bj, а по ним вычислить псевдостоимости,či,j= ai + bj для каждойсвободной клетки.
 
Таблица №5ПН / ПО
В1
В2
В3
В4
В5
ai
А1
10
č = 7
8
č = 6
5
42
6
6
9
č = 6
a1= 0
А2
6
4
7
č = 5
8
č = 4
6
č = 5
5
26
a2= — 1
А3
8
č = 8
7
27
10
č = 6
8
č = 7
7
a3= 1
А4
7
14
5
č = 6
4
č = 5
6
6
8
č = 6
a4= 0
bj
b1= 7
b2= 6
b3= 5
b4= 6
b5= 6
a4 = 0, ®
b4 = 6, так как a4+ b4= С44 = 6, ®
a1= 0, так как a1+ b4= С14 = 6, ®
b3 = 5, так как a1+ b3= С13 = 5, ®
b1 = 7, так как a4+ b1= С41 = 7, ®
a2= — 1, так как a2+ b1= С21 = 6, ®
b5 = 6, так как a2+ b5= С25 = 5, ®
a3= 1, так как a3+ b5= С35 = 7, ®
b2 = 6, так как a3+ b2= С25 = 7.
Если оказалось, что все эти псевдостоимости не превосходят стоимостейčij £ сij, £ ³ то план потенциалени, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость большестоимости (как в нашем примере), то план не является оптимальным и может быть улучшенпереносом перевозок по циклу, соответствующему данной свободной клетке. Цена этогоцикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке.В таблице № 5 мы получили в двух клетках čij ³ сij,теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строитьцикл в той клетке, в которой разность čij — сij максимальна.В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построенияцикла выберем, например, клетку (4,2):
Таблица №6
ПН
ПО
В1
В2
В3
В4
В5
ai
А1 10 8
5
42
6
6 9
А2
6 +
4 7 8 6
5 —
26 -1
А3 8
7 —
27 10 8
7 + 1
А4
7 —
14
5 +
û 4
6
6 8
bj 7 6 5 6 6
Теперь будем перемещать по циклу число 14, так как оно являетсяминимальным из чисел, стоящих в клетках, помеченных знаком —. При перемещении мыбудем вычитать 14 из клеток со знаком — и прибавлять к клеткам со знаком +. Послеэтого необходимо подсчитать потенциалы ai и bj ицикл расчетов повторяется.
Итак, мы приходим к следующему алгоритму решения транспортнойзадачи методом потенциалов.
1. Взять любой опорный план перевозок, в котором отмеченыm +n — 1 базисных клеток (остальные клетки свободные).
2. Определить для этого плана платежи (aiи bj) исходя из условия, чтобы в любой базисной клеткепсевдостоимости были равны стоимостям. Один из платежей можно назначитьпроизвольно, например, положить равным нулю.
3. Подсчитать псевдостоимости či,j= ai + bj для всех свободных клеток. Если окажется, чтовсе они не превышают стоимостей, то план оптимален.
4. Если хотя бы в одной свободной клетке псевдостоимостьпревышает стоимость, следует приступить к улучшению плана путём переброски перевозокпо циклу, соответствующему любой свободной клетке с отрицательной ценой (для которойпсевдостоимость больше стоимости).
5. После этого заново подсчитываются платежи и псевдостоимости,и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, покане будет найден оптимальный план. Так в нашем примере после 2 циклов расчетов получимоптимальный план. При этом стоимость всей перевозки изменялась следующим образом:F0= 723, F1 = 709, F2 = Fmin = 703.
Следует отметить так же, что оптимальный план может иметь и другойвид, но его стоимость останется такой же Fmin = 703.
Составьте оптимальный план перевозки угля с минимальными транспортнымирасходами с шахт Варгашорская (В), Западная (З) и Комсомольская (К), еженедельнодобывающих соответственно 26,32 и 17тыс. т. Покупатели угля расположены в разныхгородах В, В, С и D, заявки которых составляют 28, 19, 12и 16 тыс. т между поставщиками и потребителями представлены транспортной таблицей.Шахты Потребители
Добыча угля,
тыс. тонн в неделю A B C D Западная 70 76 72 68 32 Варгашорская 80 84 82 77 26 Комсомольская 80 83 82 76 17 Заявки, тыс. тонн 28 19 12 16
Решение:
Математическая модель данной задачи имеет вид:
F = 70х11+76х12+72х13+68х14+80х21+84х22+82х23+77х24+80х9+83х10 +82х11+76х12→min
/>
Экранная форма для ввода условий задачи вместе с введенными внее исходными данными представлена на рисунке:
/>
При введении зависимостей лист MS Excel в режиме просмотра формулимеет вид:
/>
После отражения закономерностей экранная форма принимает вид:
/>
Окно "Поиск решения" после ввода всех необходимыхданных задачи имеет следующий вид:
/>
Оптимальное решение задачи в экранной форме имеет вид:
/>
 
Минимальные транспортные расходы на перевозку угля равны 5715.
Заключение
В курсовой работе изложены основные подходы и методы решениятранспортной задачи, являющейся одной из наиболее распространенных задач линейногопрограммирования. Решение данной задачи позволяет разработать наиболее рациональныепути и способы транспортирования товаров, устранить чрезмерно дальние, встречные,повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затратыпредприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами,топливом, оборудованием и т.д.
Алгоритм и методы решения транспортной задачи могут быть использованыпри решении некоторых экономических задач, не имеющих ничего общего с транспортировкойгруза. В этом случае величины тарифов cij имеют различный смысл в зависимости отконкретной экономической задачи. К таким задачам относятся следующие: оптимальноезакрепление за станками операций по обработке деталей. В них cij является такимэкономическим показателем, как производительность. Задача позволяет определить,сколько времени и на какой операции нужно использовать каждый из станков, чтобыобработать максимальное количество деталей. Так как транспортная задача требуетнахождения минимума, то значения cij берутся с отрицательным знаком; оптимальныеназначения, или проблема выбора. Имеется m механизмов, которые могут выполнять mразличных работ с производительностью cij. Задача позволяет определить, какой механизми на какую работу надо назначить, чтобы добиться максимальной производительности;задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировкупродукции; увеличение производительности автомобильного транспорта за счет минимизациипорожнего пробега. Уменьшение порожнего пробега сократит количество автомобилейдля перевозок, увеличив их производительность; решение задач с помощью метода запрещенияперевозок. Используется в том случае, если груз от некоторого поставщика по каким-топричинам не может быть отправлен одному из потребителей. Данное ограничение можноучесть, присвоив соответствующей клетке достаточно большое значение стоимости, темсамым в эту клетку не будут производиться перевозки. Таким образом, важность решенияданной задачи для экономики несомненна. Приятно осознавать, что у истоков созданиятеории линейного программирования и решения, в том числе и транспортной задачи,стоял русский ученый — Леонид Витальевич Канторович.
Список используемой литературы
1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программированияМ.; Наука, 1976 г.
2. Карманов В.Г. Математическое программирование. — М.; Наука, 1986г.
3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. — М.; Наука,1978г.
4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. — М.; Наука, 1979г.
5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. — М.; Наука, 1986г