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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…………………………………………………………………… 4

1.ТРАНСПОРТНАЯ ЗАДАЧА………………………………………………. 5

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

1.2 Нахождение исходного  опорного решения……………………... 8

1.3 Проверка найденного  опорного решения на оптимальность…... 9

1.4 Переход от одного  опорного решения к другому………………. 9

2. РЕШЕНИЕ ТРАНСПОРТНЫХ  ЗАДАЧ…………………………………. 10

2.1 Пример решения задачи  транспортным методом………………. 10

2.2 Экономический вывод  задачи……………………………………. 19

ЗАКЛЮЧЕНИЕ………………………………………………………………. 20

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ ………………………………………………...21

ВВЕДЕНИЕ

Я выбрал эту тему курсовой работы, потому что каждый человек, ежедневно не всегда осознавая это  решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь  наибольшего эффекта, имея ограниченные средства, надо составить план, или  программу действий. В середине ХХ века был создан специальный математический аппарат помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.

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

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

Для реализации данной цели в работе необходимо решить следующие  задачи;

-рассмотреть транспортную  задачу, общую постановку, цели, задачи;

-изучить основные типы, виды моделей;

-охарактеризовать методы  решения транспортной задачи;

-проанализировать метод  потенциалов как метод решения  транспортных задач.

1.ТРАНСПОРТНАЯ ЗАДАЧА

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

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

          В общем виде задачу можно  представить следующим образом:  в m пунктах производства A1, A2 ,…, Am имеется однородный груз в количестве соответственно a1, a2,…,am. Этот груз необходимо доставить в n пунктов назначения B1, B2,…, Bn в количестве соответственно b1, b2,…, bn. Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна cij.

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

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

Если

то задача называется закрытой. Если

то открытой.

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

Таблица 1

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

при ограничениях:

Оптимальным решением задачи является матрица

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

- нахождение исходного  опорного решения

- проверка этого решения  на оптимальность

- переход от одного  опорного решения к другому

Рассмотрим каждый из этих этапов.

1.2 Нахождение исходного  опорного решения

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

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

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

Найденное исходное опорное  решение проверяется на оптимальность  методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему  соответствует система m+n действительных чисел ui и vj, удовлетворяющих условиям ui + vj= cij, для занятых клеток и ui +vi – cij ≤ 0 для свободных клеток. Одному из потенциалов дается произвольное значение, например u1 = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал vj, то ui = cij - vj.

Обозначим ∆ij = ui+vj-cij. Эту оценку называют оценкой свободных клеток. Если ∆ij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок ∆ij > 0, то опорное решение не является оптимальным и его можно улучшить перейдя от одного опорного решения к другому.

1.4 Переход от одного  опорного решения к другому

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

Для свободной клетки с  ∆ij > 0 строится цикл (цепь, многоугольник), все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. с тех пор, пока не получим оптимальное решение.

2. РЕШЕНИЕ ТРАНСПОРТНЫХ  ЗАДАЧ

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

В качестве примера возьмём  следующую задачу:

Четыре предприятия данного  технологического района для производства продукции используют три вида сырья, потребности в сырье каждого  из предприятий соответственно равны  150, 120, 80, 50 единиц. Сырьё сосредоточено в трёх местах его получения, а запасы соответственно  100, 130, 170 единиц. Тарифы перевозок известны и заданы матрицей:

Для начала выясним, какая  это задача, а для этого сравним  общее количество сырья на складах  и общее количество потребления:

А = 100+130+170=400

В = 150+120+80+50 = 400

А = В – из этого следует, что задача является закрытой.

Шаг 1.

Составим таблицу, расставим  тарифы и сделаем распределение:

Таблица 2

Распределение выполнили. Можно  найти коэффициент затрат на перевозки  сырья F. С ходом решения этот коэффициент должен только уменьшаться, по сравнению с предыдущим.

 F = 2*100+5*30+3*80+7*40+14*80 = 2290 единиц.

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

c_ij=u_i+v_j

В итоге у нас получится  вот такая таблица:

Таблица 3

Теперь мы можем выяснить, можем ли мы уменьшить коэффициент  F, а для этого теперь работает с пустыми клетками.

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

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

∆₁₂ = 0+0-1=(-1)

∆₁₃ = 0+7-8=(-1)

∆₁₄ = 0-3-12=(-15)

∆₂₃ = 3+7-7=3

∆₂₄ = -3+3-5=(-5)

∆₃₁ = 2+7-3=6

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

Вернёмся к самой таблице  и возьмём выбранную нами клетку как 1 из вершин прямоугольника. Теперь перед нами стоит задача: составить  прямоугольник, у которого 3 вершины  будут являться заполненными клетками, но наша 1 выбранная вершина будет, как очевидно, принадлежать пустой клетке. Согласно их физическому расположению, вырисуем для удобства этот прямоугольник и вынесем на его вершины значения выбранных клеток. Присвоим вершине со значением 0 и вершине, противоположной вершине со значением 0 – знак «+», что означает, что вершины положительные, а остальным вершинам знак «-», что значит вершины отрицательные, т. е. получится вот так:

 Среди 2 отрицательных  вершин находим наименьшее число.  В данном примере это число  40. Теперь к положительным вершинам прибавляем это число, а из отрицательных - отнимаем. Получится так:

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

Шаг 2.

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

Составим таблицу, расставим  тарифы и сделаем распределение:

Таблица 4

Найдём коэффициент F:

F = 2*100+3*120+7*10+3*50+14*70+4*50=1960 единиц.

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

Теперь выясним оптимальность  этого решения, оценив свободные  клетки.

∆₁₂ = 0+0-1=(-1)

∆₁₃ = 13+0-8=5

∆₁₄ = 3+0-12=(-9)

∆₂₁ = 2+3-5 =0

∆₂₄ =3+3-5=1

∆₃₂ = 0+1-7=(-6)

Положительное значение у  клетки (1;3) – с ним и станем производить цикл.

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

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

Шаг 3.

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

Составим таблицу, расставим  тарифы и сделаем распределение:

Таблица 5

Найдём коэффициент F:

F = 2*30+3*120+8*70+3*120+7*10+3*120+4*50=1610 единиц.

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

Теперь выясним оптимальность  этого решения, оценив свободные  клетки.

∆₁₂ = 4+0-1=3

∆₁₄ = 3+0-12=(-9)

∆₂₁ = 2+(-1)-5=(-4)

∆₂₄ = 3+(-1)-5=(-3)

∆₃₂ =4+1-7=(-2)

∆₃₃ = 8+1-14=(-5)

Положительное значение у  клетки (1;2) – с ним и станем производить цикл.

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

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

Шаг 4.

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

Составим таблицу, расставим  тарифы и сделаем распределение:

Таблица 6

Найдём коэффициент F:

F = 2*30+1*70+3*50+7*80+3*120+4*50=1400 единиц.

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

Теперь выясним оптимальность  этого решения, оценив свободные  клетки.

∆₁₃ = 5+0-8=(-3)

∆₁₄ = 3+0-12=(-9)

∆₂₁ = 2+2-5=(-1)

∆₂₄ = 3+2-5=0

∆₃₂ =1+1-7=(-5)

∆₃₃ = 5+1-14=(-8)

Положительных чисел нет, мы нашли оптимальное решение  этой задачи.

2.2 Экономический вывод задачи

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

На целых 39% снизили стоимость перевозки:

1. Потребителю b1, потребовалось взять 30 единиц сырья со склада a1 и 120 единиц сырья со склада a3;
2. Потребителю b2, потребовалось взять 70 единиц сырья со склада a1 и 50 единиц сырья со склада a2;
3. Потребителю b3, потребовалось взять 80 единиц сырья со склада a2;
4. Потребителю b4, потребовалось взять 50 единиц сырья со склада a3.

ЗАКЛЮЧЕНИЕ

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

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.
2. Баумоль. У. Экономическая теория и исследование операций. – М.; Наука, 2004.
3. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.
4. Боровков А.А. Математическая статистика. М.: Наука, 2004.
5. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. – М.: Высшая школа, 2004.