Реферат Математическая постановка транспортной задачи линейного программирования и решение её различным
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ СИСТЕМ
КАФЕДРА «Моделирование и математические методы в экономике»
КУРСОВАЯ РАБОТА
по дисциплине:
«Математическая экономика»
на тему:
«Математическая постановка транспортной задачи линейного
программирования и решение её различными методами».
ВЫПОЛНИЛА: ст-ка 3 курса гр.и-711
Бегова Илина Б.
ПРОВЕРИЛ: к.ф.-м.н.доцент
Атагишиева Г.С.
Махачкала 2010
Содержание
Введение…………………………………………………………………………………….3
Глава 1. Постановка и модели транспортной задачи линейного программирования………………………………………………………………...………5
1.1. Постановка транспортной задачи и ее математическая модель………..5
1.2. Закрытая модель транспортной задачи……………………………………..9
1.3. Открытая модель транспортной задачи…………………………………….10
Глава 2. Методы нахождения опорных и оптимальных планов………………12
2.1. Определение оптимального и опорного плана транспортной задачи…..12
2.2.Метод северо-западного угла……………………………………………………14
2.3. Метод минимального элемента……………………………………………….16
2.4. Метод аппроксимации Фогеля…………………………………………………19
2.5. Метод потенциалов………………………………………………………………21
Приложение……………………………………………………………………………..22
Заключение………………………………………………………………………………34
Список литературы…………………………………………………………………..36
Введение
Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий.
Раньше план в таких случаях составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке».
Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах («линейное программирование, динамическое программирование» и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование». С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.
Цель заданной работы - освоить математическую постановку транспортной задачи линейного программирования.
Глава 1. Постановка и модели транспортной задачи линейного программирования.
1.1. Постановка транспортной задачи и ее математическая модель
Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) Аi …, Аm, в которых сосредоточены запасы однородных продуктов в количестве a1, ..., аm единиц. Имеется n пунктов назначения (или пунктов потребления) В1, ..., Вm, потребность которых в указанных продуктах составляет b1, ..., bn единиц. Известны также транспортные расходы Сij, связанные с перевозкой единицы продукта из пункта Ai в пункт Вj, i
т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.
Пусть хij - количество единиц продукта, поставляемого из пункта Аi в пункт Вj. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:
Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что
Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности. Это условие полного удовлетворения спроса:
Объемы перевозок - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:
xij
Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления.
Определение 1.
Всякое неотрицательное решение системы линейных уравнений
определяемое матрицей X=(xij)(i
Определение 2.
принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
Обычно исходные данные записываются в виде таблицы 1.
| Пункты отправления | Пункты назначения | Запасы | ||||
| В1 | … | Bj | … | Bn | А1 | |
| A1 | C11 X11 | … | C1j X1j | … | C1n X1n | a1 |
| … | … | … | … | … | … | … |
| Ai | Ci1 Xi1 | … | Cij Xij | … | Cin Xin | ai |
| … | … | … | … | … | … | … |
| Am | Cm1 Xm1 | … | Cmj Xmj | … | Cmn Xmn | am |
| Потребности | b1 | … | bj | … | bn | |
Очевидно, общее наличие груза у поставщиков равно
то модель такой транспортной задачи называется закрытой.
В ряде случаев не требуется, чтобы весь произведенный продукт в каждом пункте производства был реализован. В таких случаях баланс производства и потребления может быть нарушен:
Введение этого условия приводит к открытой транспортной модели.
Теорема 1.
Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.
1.2. Закрытая модель транспортной задачи
Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена.
Доказательство. Пусть
Тогда величины xij
= aibj
/M (i
= 1,2,3, ... m; j
= 1,2,3, ..., n) являются планом, так как они удовлетворяют системе ограничений
( 2 ) и ( 3 ) .
Действительно, подставляя значения в (2) и (3) , находим
Выберем из значений Cij наибольшее C¢ = max
Cij и заменим в линейной функции ( 1 ) все коэффициенты на C¢ тогда, учитывая ( 2 ) , получим
Выберем из значений Cij наименьшее C
¢¢
=
min
Cij и заменим в линейной функции все коэффициенты на C
¢¢ ; тогда, учитывая ( 2 ) имеем
Объединяя два последних неравенства в одно двойное, окончательно получаем
C
¢¢
M
?
Z
?
C
¢
M,
т. е. линейная функция ограничена на множестве планов транспортной задачи.
1.3. Открытая модель транспортной задачи
Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие
a) суммарные запасы превышают суммарные потребности
b) суммарные потребности превышают суммарные запасы
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Найти минимальное значение линейной функции
xij ³
0 (i = 1, 2, ..., m; j = 1, 2, ..., n).
Открытая модель решается приведением к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1 =
суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1 =
Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
После преобразований задача принимает вид закрытой модели и решается обычном способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика.
Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала проверить, к какой модели она принадлежит, и только после этого составить таблицу для ее решения.
Глава 2. Методы нахождения опорных и оптимальных планов.
2.1. Определение оптимального и опорного плана транспортной задачи
Как и при решении задачи линейного программирования, симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана.
Число переменных Xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (2) и (3) равно n+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных.
Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше - то выраженным.
Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже.
При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ.
Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.
Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Одна из них - метод потенциалов - рассматривается ниже.
2.2.Метод северо-западного угла
При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного
Пример.
| 70 | 50 | 15 | 80 | 70 | 300 |
| 80 | 90 | 40 | 60 | 85 | 150 |
| 50 | 10 | 90 | 11 | 25 | 250 |
| 170 | 110 | 100 | 120 | 200 | 700 |
Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным
Теперь переходим к заполнению клетки для неизвестного
Через шесть шагов у нас останется одна база
Опорный план имеет вид;
| 170 | 110 | 20 | 0 | 0 |
| 0 | 0 | 80 | 70 | 0 |
| 0 | 0 | 0 | 50 | 200 |
2.3. Метод минимального элемента
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел
Пример
Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
| 2 | 3 | 4 | 15 |
| 11 | 6 | 10 | 1 |
| 8 | 9 | 3 | 3 |
| 4 | 1 | 2 | 21 |
| 10 | 20 | 10 | |
Решение:
Задача сбалансирована.
Строим первоначальный опорный план методом минимального элемента.
1. Выясним минимальную стоимость перевозок.
2.
3.
4. Четвертая перевозка осуществляется с пункта
5. Пятая перевозка осуществляется с пункта
6. Шестая перевозка осуществляется с пункта
Опорный план имеет вид:
| 10 | 5 | 0 |
| 0 | 1 | 0 |
| 0 | 3 | 0 |
| 0 | 11 | 10 |
2.4. Метод аппроксимации Фогеля
При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.
Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).
Пример
Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:
(Здесь мы перенесли потребности в верхнюю строку для удобства построения плана). Рассмотрим задачу, приведенную для методов северо-западного угла и минимального элемента
Решение:
| 10 | 20 | 10 | | | | |
| 2 7 | 3 0 | 4 8 | 15 | 1 | 1 | 1 |
| 11 0 | 6 1 | 10 0 | 1 | 4 | 4 | - |
| 8 3 | 9 0 | 3 0 | 3 | 5 | - | - |
| 4 0 | 1 19 | 2 2 | 21 | 1 | 1 | - |
| 2 | 2 | 1 | ||||
| 2 | 2 | 2 | ||||
| 2 | 2 | 2 | ||||
| 2 | - | 2 | ||||
| - | - | 2 | ||||
| - | - | - | ||||
Опорный план имеет вид:
| 7 | 0 | 8 |
| 0 | 1 | 0 |
| 3 | 0 | 0 |
| 0 | 19 | 2 |
2.5. Метод потенциалов
Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:
vj[k] – ui[k] Cij, i 1, ..., m; j 1, …, п.
Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.
Приложение
Задача 1.
Решить следующую задачу на минимизацию транспортных затрат предприятия с использованием надстройки «Поиск решения» электронной таблицы Excel.
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции из i-го пункта производства в j-ый центр потребления Cij приведена в таблице, где под строкой понимается пункт производства, а под столбцом -пункт потребления. Кроме того, в таблицах в i-й строке указан объем производства в i-м пункте, а в j-м столбце указан спрос в j-м центре потребления. Составить план перевозок по доставке требуемой продукции в пункты потребления, минимизирующий суммарные транспортные расходы. Необходимые данные для решения задачи взять из представленной ниже таблицы. Таблица1
| Предприятия | Стоимость перевозки единицы продукции | Объем произ-водства | |||
| Пункты потребления | |||||
| 1 | 2 | 3 | 4 | ||
| А | 7,3 | 9 | 3 | 10 | 14 |
| В | 3 | 10 | 3 | 9 | 30 |
| С | 7 | 11 | 3 | 2 | 20 |
| D | 8 | 5 | 9 | 2 | 32 |
| E | 4,8 | 9 | 10 | 5 | 16 |
| Объемы потребления | 60 | 10 | 20 | 10 | |
.
1) Переменные задачи. Обозначим количество продукции, которые будут перевозиться из n пунктов производства в m пункты потребления как Xij (i=1,2,3,4,5,6; j=1,2,3,4,5). Это переменные задачи, значения которых должны быть определены в процессе решения.
В задаче содержится 6*5=30 переменных.
2) Ограничения на переменные задачи. Очевидно, что все переменные задачи не отрицательные, т.е.
Xij
где i=1, 2, 3,4,5,; j=1, 2, 3, 4.
Обычно транспортная задача представляется в виде таблицы, где в ячейках помещаются переменные задачи ( Xij ), а в правом верхнем углу ячейки стоят стоимости перевозки из пункта i в пункт j ( Cij ). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи .
Транспортная задача, для которой суммы чисел в последнем столбце и нижней строке равны, называется сбалансированной: 15 + 25 + 5 = 45, 5 + 15 + 15 + 10 = 45. Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец. Причем стоимости перевозки в добавленных ячейках принимаются равными нулю.
Для нашего примера транспортная задача не сбалансирована. Сумма чисел в последнем столбце равна: 14+30+20+32+16=112, а нижней строке равна: 60+10+20+10=100. Чтобы сбалансировать задачу вводим пятый столбец и добавляем туда 12. Таблица в этом случае имеет вид:
| | Стоимость перевозки единицы продукции | Объем производства | ||||
| Предприятия | Пункты потребления | |||||
| | 1 | 2 | 3 | 4 | 5 | |
| A | 7,3 | 9 | 3 | 10 | 0 | 14 |
| B | 3 | 10 | 3 | 9 | 0 | 30 |
| C | 7 | 11 | 3 | 2 | 0 | 20 |
| D | 8 | 5 | 9 | 2 | 0 | 32 |
| E | 4,8 | 9 | 10 | 5 | 0 | 16 |
| Объемы потребления | 60 | 10 | 20 | 10 | 12 | |
3) Целевая функция. Транспортные расходы на перевозку по доставке требуемой продукции вычисляются по формуле:
Z =
II
. Решение транспортной задачи в процедуре
EXCEL
“Поиск решения”
1) Ввод данных. Вводим данные таблицы 1 и 2 в ячейки EXCEL.
В ячейках B4 : E7 введены стоимости перевозок (табл. 1).
В ячейках G4: G8 находится объемы производства. А в ячейках B9: F12 находится объемы потребления. Ячейки B11 : F15 – рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи Xij.
В ячейках G11 : G15 нужно записать формулы для вычисления левых частей ограничений:
в G11 должна быть сумма ячеек B11 : F11;
в G12 должна быть сумма ячеек B12 : F12;
в G13 должна быть сумма ячеек B13 : F13;
в G14 должна быть сумма ячеек B14 : F14;
в G15 должна быть сумма ячеек B15 : F15. .
Формулы для вычисления левых частей ограничений введем в ячейки B16 : F16:
в C16 должна быть сумма ячеек C11 : C15;
в D16 должна быть сумма ячеек D11: D15;
в E16 должна быть сумма ячеек E11: E15;
в F16 должна быть сумма ячеек F11 : F15;
Целевую функцию поместим в ячейку H9:
H9: СУММПРОИЗВ (B4 : F8; B12: F16).
Таблица исходных данных имеет вид :
2) Заполнение окна процедуры «Поиск решения».
целевая функция H9;
значение целевой функции : min;
изменяемые ячейки : B12:F16;
ограничения задачи :
G12:G16=G4:G8
B12:F16 = B4:F8
B12 : F16
3) Выполнив процедуру «Поиск решения» получим следующие результаты:
Вывод:
Таким образом с предприятия А(исходный пункт 1) следует 14 ед.продукции в пункты потребления 3(пункт назначения 3); из предприятия В(исходный пункт 2) 30 ед.продукции отвести в пункт потребления 1(пункт назначения 1); из предприятия С(исходный пункт 3) 14 ед.продукции отвести в пункт потребления 1(пункт назначения 1) и 6 ед.продукции отвести в пункт потребления 3(пункт назначения 3); из предприятия D(исходный пункт 4)7,21E-07 ед.продукции отвести в пункт потребления 1(пункт назначения 1) , 10 ед.продукции отвести в пункт потребления 2(пункт назначения 2), 10 ед.продукции отвести в пункт потребления 4(пункт назначения 4) и 12 ед.продукции отвести в пункт потребления 5(пункт назначения 5); из предприятия Е(исходный пункт 5) 16 ед.продукции отвести в пункт потребления 1(пункт назначения 1).
Все эти результаты видны в конечной таблице. При этом суммарная стоимость транспортных расходов составит 394,8 рублей (ячейка Н9).
Задача 2.
Найти опорный план транспортной задачи, в которой запасы на 3-х складах равны 210, 170, и 65 единиц, а потребности 4-х магазинов равны 125, 90, 130 и 100 единиц продукции. Тарифы перевозки в рублях за единицу продукции следующие:
5 8 1 2
2 5 4 9
9 2 3 1
Решение методом северо-западного угла
| Пункты Отправления | Пункты назначения | Запасы | |||||||||
| | | | | | |||||||
| | | 5 | | 8 | | 1 | | 9 | 210/85/0 | ||
| 125 | 85 | | | ||||||||
| | | 2 | | 5 | | 4 | | 9 | 170/165/35/0 | ||
| | 5 | 130 | 35 | ||||||||
| | | 9 | | 2 | | 3 | | 1 | 65/0 | ||
| | | | 65 | ||||||||
| Потребности | 125/0 | 90/5/0 | 130/0 | 100/65/0 | | ||||||
125 85 0 0
0 5 130 35
0 0 0 65
F(x)=
Решение методом минимального элемента
| Пункты Отправления | Пункты назначения | Запасы | |||||||||
| | | | | | |||||||
| | | 5 | | 8 | | 1 | | 9 | 210/80/35/0 | ||
| | 45 | 130 | 35 | ||||||||
| | | 2 | | 5 | | 4 | | 9 | 170/45/0 | ||
| 125 | 45 | | | ||||||||
| | | 9 | | 2 | | 3 | | 1 | 65/0 | ||
| | | | 65 | ||||||||
| Потребности | 125/0 | 90/45/0 | 130/0 | 100/35/0 | | ||||||
Опорный план имеет вид:
0 45 130 35
125 45 0 0
0 0 0 65
F(x)=
Решение методом Фогеля
| Пункты Отпр-ия | Пункты назначения | Запасы | ||||||||||||||
| | | | | | di | |||||||||||
| | | 5 | | 8 | | 1 | | 9 | 210/110/0 | 1 | 1 | 1 | 7 | |||
| | | 110 | 100 | |||||||||||||
| | | 2 | | 5 | | 4 | | 9 | 170/45/25/0 | 2 | 1 | 1 | 1 | |||
| 125 | 25 | 20 | | |||||||||||||
| | | 9 | | 2 | | 3 | | 1 | 65/0 | 1 | 1 | | | |||
| | 65 | | | |||||||||||||
| Потр-ти | 125/0 | 90/25/0 | 130 | 100 | | |||||||||||
dj | 3 | 3 | 2 | 1 | ||||||||||||
| | 3 | 2 | 1 | |||||||||||||
| | 3 | 3 | 7 | |||||||||||||
| | 3 | 3 | | |||||||||||||
0 0 110 100
125 25 20 0
0 65 0 0
F(x)=
Задача 3
7 8 1 2
4 5 9 8
9 2 3 6
Решение методом северо-западного угла
| Пункты Отправления | Пункты назначения | Запасы | |||||||||
| | | | | | |||||||
| | | 7 | | 8 | | 1 | | 2 | 160/40/0 | ||
| 120 | 40 | | | ||||||||
| | | 4 | | 5 | | 9 | | 8 | 140/130/0 | ||
| | 10 | 130 | | ||||||||
| | | 9 | | 2 | | 3 | | 6 | 180/110/0 | ||
| | | 70 | 110 | ||||||||
| Потребности | 120/0 | 50/10/0 | 200/70/0 | 110/0 | | ||||||
Опорный план имеет вид:
120 40 0 0
0 10 130 0
0 0 70 110
F(x)=
Решение методом минимального элемента
| Пункты Отправления | Пункты назначения | Запасы | |||||||||
| | | | | | |||||||
| | | 7 | | 8 | | 1 | | 2 | 160/0 | ||
| | | 160 | | ||||||||
| | | 4 | | 5 | | 9 | | 8 | 140/20/0 | ||
| 120 | | | 20 | ||||||||
| | | 9 | | 2 | | 3 | | 6 | 180/130/90/0 | ||
| | 50 | 40 | 90 | ||||||||
| Потребности | 120/0 | 50/0 | 200/40/0 | 110/20/0 | | ||||||
0 0 160 0
120 0 0 20
0 50 40 90
F(x)=
Решение методом Фогеля
| Пункты Отпр-ия | Пункты назначения | Запасы | ||||||||||||||
| | | | | | di | |||||||||||
| | | 7 | | 8 | | 1 | | 2 | 160/50/0 | 1 | 6 | | | |||
| | | 50 | 110 | |||||||||||||
| | | 4 | | 5 | | 9 | | 8 | 140/0 | 1 | 1 | 1 | 1 | |||
| 120 | 20 | | | |||||||||||||
| | | 9 | | 2 | 150 | 3 | | 6 | 180/30/0 | 1 | 1 | 1 | 7 | |||
| | 30 | | | |||||||||||||
| Потр-ти | 120/0 | 50/20/0 | 200/150/0 | 110/0 | | |||||||||||
dj | 3 | 3 | 2 | 4 | ||||||||||||
| 3 | 3 | 2 | | |||||||||||||
| 5 | 3 | 6 | | |||||||||||||
| 5 | 3 | | | |||||||||||||
Опорный план имеет вид:
0 0 50 110
120 20 0 0
0 30 150 0
F(x)=
Таким образом, мы видим, что метод Фогеля дает наилучший результат, а метод северо-западного угла – наихудший.
Заключение
В работе изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:
- оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность.
Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;
- оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
- задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;
- увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;
- решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки.
Таким образом, важность решения данной задачи для экономики несомненна.
Список литературы
1. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.
2. Баумоль У. Экономическая теория и исследование операций. - М.; Наука, 2004.
3. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.
4. Боровков А.А. Математическая статистика. М.: Наука, 2004.
5. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 2004
6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - СПБ: Издательство «Лань», 2003.
7. Коршунов Д.А., Чернова Н.И. Сборник задач и упражнений по математической статистике. Новосибирск: Изд-во Института математики им. С.Л.Соболева СО РАН, 2001.
8. Красс М. Математика для экономических специальностей. Учебник. 3-е изд., перераб и доп. М, Экономист, 2004.
9. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе: Учебник. - 3-е изд., исп. - М.: Дело, 2002.
10. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск, Высшая школа, 2005
11. Пехелецкий И.Д. Математика: учебник для студентов. - М.: Академия, 2003.
12. Павлова Т.Н, Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.
13. Павлова Т.Н, Ракова О.А. Решение задач линейного программирования. Учебное пособие. - Димитровград, 2002
