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

Введение

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

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

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

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

Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача.

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

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

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

1. раскрыть теоретическое содержание данной темы;

2. сформулировать и найти оптимальное решение задачи.

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

1. Описание типа задачи

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа - Канторовича.

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

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

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

2. Методы решения транспортных задач

Получение начального опорного плана

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

Улучшение опорного плана

- метод потенциалов

Начальная таблица для заполнения ячеек:

	1	2	3	4	Запасы
1	3	1	3	4	10
2	5	3	2	3	15
3	2	3	4	1	25
4	6	2	5	3	10
Потребности	5	15	20	20	60/60

Метод «Северо-Западного угла».

В этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного x₁₁ и заканчивается в клетке неизвестного x_mn, т.е. идет как бы по диагонали таблицы перевозок. Заполнение таблицы начинается с ее северо-западного угла, т.е. клетки с неизвестным x₁₁. Первая база A₁ может полностью удовлетворить потребность первого заказчика B₁ (a₁=10, b₁=5, a>b). Полагая x₁₁=5, вписываем это значение в клетку x₁₁ и исключаем из рассмотрения первый столбец. На базе A₁ остается измененный запас a=5. В оставшейся новой таблице с четырьмя строками A₁, A₂, A_3,А₄ и четырьмя столбцами В₁; B₂, B₃, B₄; северо-западным углом будет клетка для неизвестного x₁₂. Первая база с запасом a₁=5 может полностью удовлетворить потребность второго заказчика B₂ a₁=5, b₂=15. Полагаем x₁₂=5, вписываем это значение в клетку х₁₂ и исключаем из рассмотрения первую строку. В оставшейся новой таблице с двумя строками A₂, A₃ и тремя столбцами B₃, B₄, B₅ северо-западным углом будет клетка для неизвестного x₂₂. Теперь второй заказчик B₂ может принять весь запас с базы A₂ (a₂=15, b₃=15, a₂b₂). Полагаем x₁₃=10, вписываем это значение в клетку x₂₂ и исключаем из рассмотрения второй столбец. У заказчика из B₂ осталась еще не удовлетворенной потребность b₂=5.

Теперь переходим к заполнению клетки для неизвестного x₂₃ и т.д. Через шесть шагов у нас останется одна база A₃ с запасом груза (остатком от предыдущего шага) a₄=10 и один пункт B₄ с потребностью b₄=20. Соответственно этому имеется одна свободная клетка, которую и заполняем, положив x₄₄=10. План составлен. Базис образован неизвестными x₁₁, x₁₂, x₂₂, x₂₃, x₃₃, x₃₄, x₄₄. Правильность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица, заполненная методом «Северо-западного угла»

Пункты отправления	B1	B2	B3	B4	Запасы
A1	5	5			10
A2		10	5		15
A3			15	10	25
A4				10	10
Потребности	5	15	20	20	60/60

Общий объем перевозок для этого плана составит:

Z= 3*5 + 1*5 + 2*15 + 4*5 + 1*20 + 2*10 = 110

3. Содержательная постановка задачи

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

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

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

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

- список мест назначения и их показатели спроса;

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

Начальные параметры задачи

Пункты отправления	B1	B2	B3	B4	Запасы
A1	3	1	3	4	10
A2	5	3	2	3	15
A3	2	3	4	1	25
A4	6	2	5	3	10
Потребности	5	15	20	20

Целевая функция имеет вид:

Ограничение по запасам:

x₁₁+x₁₂+x₁₃+x₁₄<=10

x₂₁+x₂₂+x₂₃+x₂₄<=15

x₃₁+x₃₂+x₃₃+x₃₄<=25

x₄₁+x₄₂+x₄₃+x₄₄<=10

X_ij>=0

Ограничение по спросу:

x₁₁ + x₂₁+x₃₁+x₄₁ <= 5

x₁₂ + x₂₂+x₃₂₊x₄₂ <= 15

x₁₃ + x₂₃+x₃₃+x₄₃ <= 20

x₁₄+x₂₄+x₃₄+x₄₄<=20

4. Математическая постановка задачи

Пусть требуется перевезти груз из пункта А₁, А₂,…, А_n в пункты В₁, В₂,…, В_n,а₁₁, а₁₂,…, a_nk - стоимость перевозки из пункта А_i в пункт В_j.

Пусть X_ij - количество груза перевозимого из пункта i в пункт j.

A1=10; A2=15; A3=25; A4=10; B1=5; B2=15; B3=20; B4=20;

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

Построим начальную таблицу для заполнения ячеек:

Пункты отправления	1	2	3	4	Запасы
1	5 [3]	5 [1]			10
2		10 [3]	5 [2]		15
3			15 [4]	10 [1]	25
4				10 [3]	10
Потребности	5	15	20	20	60/60

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

Z= 3*5 + 1*5 + 10*3+5*2+15*4+10*1+10*3=160

Сумма запаса и сумма потребления равны:

10+15+25+10=5+15+20+20; 60=60

5. Математическое решение задачи

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

Пункты отправления	1	2	3	4	Запасы
1	5	5			10
2		10	5		15
3			15	10	25
4				10	10
Потребности	5	15	20	20	60/60

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

?a = 10 + 15 + 25 + 10 = 60

?b = 5 + 15 + 20 + 20 = 60

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

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

	1	2	3	4	Запасы
1	3	1	3	4	10
2	5	3	2	3	15
3	2	3	4	1	25
4	6	2	5	3	10
Потребности	5	15	20	20

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

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

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

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

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

Искомый элемент равен 1

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

x₁₂ = min (10,15) = 10.

x	1	x	x	10 - 10 = 0
5	3	2	3	15
2	3	4	1	25
6	2	5	3	10
5	15 - 10 = 5	20	20	0

Искомый элемент равен 1

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

x₃₄ = min (25,20) = 20.

x	1	x	x	0
5	3	2	x	15
2	3	4	1	25 - 20 = 5
6	2	5	x	10
5	5	20	20 - 20 = 0	0

Искомый элемент равен 2

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

x₂₃ = min (15,20) = 15.

x	1	x	x	0
x	x	2	x	15 - 15 = 0
2	3	4	1	5
6	2	5	x	10
5	5	20 - 15 = 5	0	0

Искомый элемент равен 2

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

x₃₁ = min (5,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	5 - 5 = 0
x	2	5	x	10
5 - 5 = 0	5	5	0	0

Искомый элемент равен 2

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

x₄₂ = min (10,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	0
x	2	5	x	10 - 5 = 5
0	5 - 5 = 0	5	0	0

Искомый элемент равен 5

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

x₄₃ = min (5,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	0
x	2	5	x	5 - 5 = 0
0	0	5 - 5 = 0	0	0

	1	2	3	4	Запасы
1	3	1 [10]	3	4	10
2	5	3	2 [15]	3	15
3	2 [5]	3	4	1 [20]	25
4	6	2 [5]	5 [5]	3	10
Потребности	5	15	20	20

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

Строим новый план.

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

Z = 1*10 + 2*15 + 2*5 + 1*20 + 2*5 + 5*5 = 105

Искомый элемент равен 1

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

x₃₄ = min (25,20) = 20.

3	1	3	x	10
5	3	2	x	15
2	3	4	1	25 - 20 = 5
6	2	5	x	10
5	15	20	20 - 20 = 0	0

Искомый элемент равен 1

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

x₁₂ = min (10,15) = 10.

x	1	x	x	10 - 10 = 0
5	3	2	x	15
2	3	4	1	5
6	2	5	x	10
5	15 - 10 = 5	20	0	0

Искомый элемент равен 2

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

min (15,20) = 15.



x	1	x	x	0
x	x	2	x	15 - 15 = 0
2	3	4	1	5
6	2	5	x	10
5	5	20 - 15 = 5	0	0

Искомый элемент равен 2

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

x₃₁ = min (5,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	5 - 5 = 0
x	2	5	x	10
5 - 5 = 0	5	5	0	0

Искомый элемент равен 2

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

x₄₂ = min (10,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	0
x	2	5	x	10 - 5 = 5
0	5 - 5 = 0	5	0	0

Искомый элемент равен 5

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

x₄₃ = min (5,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	0
x	2	5	x	5 - 5 = 0
0	0	5 - 5 = 0	0	0

	1	2	3	4	Запасы
1	3	1 [10]	3	4	10
2	5	3	2 [15]	3	15
3	2 [5]	3	4	1 [20]	25
4	6	2 [5]	5 [5]	3	10
Потребности	5	15	20	20

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

Строим новый план.

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

Z= 1*10 + 2*15 + 2*5 + 1*20 + 2*5 + 5*5 = 105

Искомый элемент равен 2

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

x₂₃ = min (15,20) = 15.

3	1	3	4	10
x	x	2	x	15 - 15 = 0
2	3	4	1	25
6	2	5	3	10
5	15	20 - 15 = 5	20	0

Искомый элемент равен 1

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

x₁₂ = min (10,15) = 10.

x	1	x	x	10 - 10 = 0
x	x	2	x	0
2	3	4	1	25
6	2	5	3	10
5	15 - 10 = 5	5	20	0

Искомый элемент равен 1

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

x₃₄ = min (25,20) = 20.

x	1	x	x	0
x	x	2	x	0
2	3	4	1	25 - 20 = 5
6	2	5	x	10
5	5	5	20 - 20 = 0	0

Искомый элемент равен 2

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

x₃₁ = min (5,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	5 - 5 = 0
x	2	5	x	10
5 - 5 = 0	5	5	0	0

Искомый элемент равен 2

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

x₄₂ = min (10,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	0
x	2	5	x	10 - 5 = 5
0	5 - 5 = 0	5	0	0

Искомый элемент равен 5

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

x₄₃ = min (5,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	0
x	2	5	x	5 - 5 = 0
0	0	5 - 5 = 0	0	0

	1	2	3	4	Запасы
1	3	1 [10]	3	4	10
2	5	3	2 [15]	3	15
3	2 [5]	3	4	1 [20]	25
4	6	2 [5]	5 [5]	3	10
Потребности	5	15	20	20

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

Строим новый план.

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

Z = 1*10 + 2*15 + 2*5 + 1*20 + 2*5 + 5*5 = 105

Искомый элемент равен 2

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

x₃₁ = min (25,5) = 5.

x	1	3	4	10
x	3	2	3	15
2	3	4	1	25 - 5 = 20
x	2	5	3	10
5 - 5 = 0	15	20	20	0

Искомый элемент равен 1

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

x₁₂ = min (10,15) = 10.

x	1	x	x	10 - 10 = 0
x	3	2	3	15
2	3	4	1	20
x	2	5	3	10
0	15 - 10 = 5	20	20	0

Искомый элемент равен 1

Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его. x₃₄ = min (20,20) = 20.



x	1	x	x	0
x	3	2	x	15
2	x	x	1	20 - 20 = 0
x	2	5	x	10
0	5	20	20 - 20 = 0	0

Искомый элемент равен 2

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

x₂₃ = min (15,20) = 15.

x	1	x	x	0
x	x	2	x	15 - 15 = 0
2	x	x	1	0
x	2	5	x	10
0	5	20 - 15 = 5	0	0

Искомый элемент равен 2

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

x₄₂ = min (10,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	0
x	2	5	x	10 - 5 = 5
0	5 - 5 = 0	5	0	0

Искомый элемент равен 5

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

x₄₃ = min (5,5) = 5.

x	1	x	x	0
x	x	2	x	0
2	x	x	1	0
x	2	5	x	5 - 5 = 0
0	0	5 - 5 = 0	0	0

	1	2	3	4	Запасы
1	3	1 [10]	3	4	10
2	5	3	2 [15]	3	15
3	2 [5]	3	4	1 [20]	25
4	6	2 [5]	5 [5]	3	10
Потребности	5	15	20	20

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

Строим новый план.

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

F(x) = 1*10 + 2*15 + 2*5 + 1*20 + 2*5 + 5*5 = 105

Искомый элемент равен 2

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

x₄₂ = min (10,15) = 10.

3	1	3	4	10
5	3	2	3	15
2	3	4	1	25
x	2	x	x	10 - 10 = 0
5	15 - 10 = 5	20	20	0

Искомый элемент равен 1

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

x₁₂ = min (10,5) = 5.

3	1	3	4	10 - 5 = 5
5	x	2	3	15
2	x	4	1	25
x	2	x	x	0
5	5 - 5 = 0	20	20	0

Искомый элемент равен 1

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

x₃₄ = min (25,20) = 20.

3	1	3	x	5
5	x	2	x	15
2	x	4	1	25 - 20 = 5
x	2	x	x	0
5	0	20	20 - 20 = 0	0

Искомый элемент равен 2

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

x₂₃ = min (15,20) = 15.

3	1	3	x	5
x	x	2	x	15 - 15 = 0
2	x	4	1	5
x	2	x	x	0
5	0	20 - 15 = 5	0	0

Искомый элемент равен 2

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

x₃₁ = min (5,5) = 5.

x	1	3	x	5
x	x	2	x	0
2	x	x	1	5 - 5 = 0
x	2	x	x	0
5 - 5 = 0	0	5	0	0

Искомый элемент равен 3

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

x₁₃ = min (5,5) = 5.

x	1	3	x	5 - 5 = 0
x	x	2	x	0
2	x	x	1	0
x	2	x	x	0
0	0	5 - 5 = 0	0	0

	1	2	3	4	Запасы
1	3	1 [5]	3 [5]	4	10
2	5	3	2 [15]	3	15
3	2 [5]	3	4	1 [20]	25
4	6	2 [10]	5	3	10
Потребности	5	15	20	20

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

Строим новый план.

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

Z= 1*5 + 3*5 + 2*15 + 2*5 + 1*20 + 2*10 = 100

Искомый элемент равен 3

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

x₁₁ = min (10,5) = 5.

3	1	3	4	10 - 5 = 5
x	3	2	3	15
x	3	4	1	25
x	2	5	3	10
5 - 5 = 0	15	20	20	0

Искомый элемент равен 1

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

x₁₂ = min (5,15) = 5.

3	1	x	x	5 - 5 = 0
x	3	2	3	15
x	3	4	1	25
x	2	5	3	10
0	15 - 5 = 10	20	20	0

Искомый элемент равен 1

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

x₃₄ = min (25,20) = 20.

3	1	x	x	0
x	3	2	x	15
x	3	4	1	25 - 20 = 5
x	2	5	x	10
0	10	20	20 - 20 = 0	0

Искомый элемент равен 2

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

x₂₃ = min (15,20) = 15.

3	1	x	x	0
x	x	2	x	15 - 15 = 0
x	3	4	1	5
x	2	5	x	10
0	10	20 - 15 = 5	0	0

Искомый элемент равен 2

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

x₄₂ = min (10,10) = 10.

3	1	x	x	0
x	x	2	x	0
x	x	4	1	5
x	2	x	x	10 - 10 = 0
0	10 - 10 = 0	5	0	0

Искомый элемент равен 4

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

x₃₃ = min (5,5) = 5.

3	1	x	x	0
x	x	2	x	0
x	x	4	1	5 - 5 = 0
x	2	x	x	0
0	0	5 - 5 = 0	0	0

	1	2	3	4	Запасы
1	3 [5]	1 [5]	3	4	10
2	5	3	2 [15]	3	15
3	2	3	4 [5]	1 [20]	25
4	6	2 [10]	5	3	10
Потребности	5	15	20	20

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

Строим новый план.

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

Z = 3*5 + 1*5 + 2*15 + 4*5 + 1*20 + 2*10 = 110

Искомый элемент равен 3

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

x₁₃ = min (10,20) = 10.

x	x	3	x	10 - 10 = 0
5	3	2	3	15
2	3	4	1	25
6	2	5	3	10
5	15	20 - 10 = 10	20	0

Искомый элемент равен 1

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

x₃₄ = min (25,20) = 20.

x	x	3	x	0
5	3	2	x	15
2	3	4	1	25 - 20 = 5
6	2	5	x	10
5	15	10	20 - 20 = 0	0

Искомый элемент равен 2

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

x₂₃ = min (15,10) = 10.

x	x	3	x	0
5	3	2	x	15 - 10 = 5
2	3	x	1	5
6	2	x	x	10
5	15	10 - 10 = 0	0	0

x₂₃ = min (15,10) = 10.

Искомый элемент равен 2

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

x₃₁ = min (5,5) = 5.



x	x	3	x	0
x	3	2	x	5
2	x	x	1	5 - 5 = 0
x	2	x	x	10
5 - 5 = 0	15	0	0	0

Искомый элемент равен 2

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

x₄₂ = min (10,15) = 10.

x	x	3	x	0
x	3	2	x	5
2	x	x	1	0
x	2	x	x	10 - 10 = 0
0	15 - 10 = 5	0	0	0

Искомый элемент равен 3

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

x₂₂ = min (5,5) = 5.

x	x	3	x	0
x	3	2	x	5 - 5 = 0
2	x	x	1	0
x	2	x	x	0
0	5 - 5 = 0	0	0	0

	1	2	3	4	Запасы
1	3	1	3 [10]	4	10
2	5	3 [5]	2 [10]	3	15
3	2 [5]	3	4	1 [20]	25
4	6	2 [10]	5	3	10
Потребности	5	15	20	20

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

Строим новый план.

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

Z = 3*10 + 3*5 + 2*10 + 2*5 + 1*20 + 2*10 = 115

Искомый элемент равен 3

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

x₂₂ = min (15,15) = 15.

3	x	3	4	10
x	3	x	x	15 - 15 = 0
2	x	4	1	25
6	x	5	3	10
5	15 - 15 = 0	20	20	0

Искомый элемент равен 1

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

x₃₄ = min (25,20) = 20.

3	x	3	x	10
x	3	x	x	0
2	x	4	1	25 - 20 = 5
6	x	5	x	10
5	0	20	20 - 20 = 0	0

Искомый элемент равен 2

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

x₃₁ = min (5,5) = 5.

x	x	3	x	10
x	3	x	x	0
2	x	x	1	5 - 5 = 0
x	x	5	x	10
5 - 5 = 0	0	20	0	0

Искомый элемент равен 3

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

x₁₃ = min (10,20) = 10.

x	x	3	x	10 - 10 = 0
x	3	x	x	0
2	x	x	1	0
x	x	5	x	10
0	0	20 - 10 = 10	0	0

Искомый элемент равен 5

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

x₄₃ = min (10,10) = 10

x	x	3	x	0
x	3	x	x	0
2	x	x	1	0
x	x	5	x	10 - 10 = 0
0	0	10 - 10 = 0	0	0

	1	2	3	4	Запасы
1	3	1	3 [10]	4	10
2	5	3 [15]	2	3	15
3	2 [5]	3	4	1 [20]	25
4	6	2	5 [10]	3	10
Потребности	5	15	20	20

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

Строим новый план.

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

Z= 3*10 + 3*15 + 2*5 + 1*20 + 5*10 = 155

Искомый элемент равен 3

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

x₂₄ = min (15,20) = 15.

3	1	3	4	10
x	x	x	3	15 - 15 = 0
2	3	4	1	25
6	2	5	3	10
5	15	20	20 - 15 = 5	0

Искомый элемент равен 1

Для этого элемента запасы равны 10, потребности 15. Поскольку минимальным является 10, то вычитаем его. x₁₂ = min (10,15) = 10.

x	1	x	x	10 - 10 = 0
x	x	x	3	0
2	3	4	1	25
6	2	5	3	10
5	15 - 10 = 5	20	5	0

Искомый элемент равен 1

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

x₃₄ = min (25,5) = 5.

x	1	x	x	0
x	x	x	3	0
2	3	4	1	25 - 5 = 20
6	2	5	x	10
5	5	20	5 - 5 = 0	0

Искомый элемент равен 2

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

x₃₁ = min (20,5) = 5.

x	1	x	x	0
x	x	x	3	0
2	3	4	1	20 - 5 = 15
x	2	5	x	10
5 - 5 = 0	5	20	0	0

Искомый элемент равен 2

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

x₄₂ = min (10,5) = 5.



x	1	x	x	0
x	x	x	3	0
2	x	4	1	15
x	2	5	x	10 - 5 = 5
0	5 - 5 = 0	20	0	0

Искомый элемент равен 4

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

x₃₃ = min (15,20) = 15.

x	1	x	x	0
x	x	x	3	0
2	x	4	1	15 - 15 = 0
x	2	5	x	5
0	0	20 - 15 = 5	0	0

Искомый элемент равен 5

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

x₄₃ = min (5,5) = 5.

x	1	x	x	0
x	x	x	3	0
2	x	4	1	0
x	2	5	x	5 - 5 = 0
0	0	5 - 5 = 0	0	0

	1	2	3	4	Запасы
1	3	1 [10]	3	4	10
2	5	3	2	3 [15]	15
3	2 [5]	3	4 [15]	1 [5]	25
4	6	2 [5]	5 [5]	3	10
Потребности	5	15	20	20

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

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

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

Z= 1*10 + 3*15 + 2*5 + 4*15 + 1*5 + 2*5 + 5*5 = 165

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

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

u₁ + v₂ = 1; 0 + v₂ = 1; v₂ = 1

u₄ + v₂ = 2; 1 + u₄ = 2; u₄ = 1

u₄ + v₃ = 5; 1 + v₃ = 5; v₃ = 4

u₃ + v₃ = 4; 4 + u₃ = 4; u₃ = 0

u₃ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₃ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

u₂ + v₄ = 3; 1 + u₂ = 3; u₂ = 2

	v1=2	v2=1	v3=4	v4=1
u1=0	3	1 [10]	3	4
u2=2	5	3	2	3 [15]
u3=0	2 [5]	3	4 [15]	1 [5]
u4=1	6	2 [5]	5 [5]	3

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

(1; 3): 0 + 4 > 3; ?₁₃ = 0 + 4 - 3 = 1

(2; 3): 2 + 4 > 2; ?₂₃ = 2 + 4 - 2 = 4

max (1,4) = 4

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

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

	1	2	3	4	Запасы
1	3	1 [10]	3	4	10
2	5	3	2 [+]	3 [15] [-]	15
3	2 [5]	3	4 [15] [-]	1 [5] [+]	25
4	6	2 [5]	5 [5]	3	10
Потребности	5	15	20	20

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

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

	1	2	3	4	Запасы
1	3	1 [10]	3	4	10
2	5	3	2 [15]	3	15
3	2 [5]	3	4 [0]	1 [20]	25
4	6	2 [5]	5 [5]	3	10
Потребности	5	15	20	20

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

u₁ + v₂ = 1; 0 + v₂ = 1; v₂ = 1

u₄ + v₂ = 2; 1 + u₄ = 2; u₄ = 1

u₄ + v₃ = 5; 1 + v₃ = 5; v₃ = 4

u₂ + v₃ = 2; 4 + u₂ = 2; u₂ = -2

u₃ + v₃ = 4; 4 + u₃ = 4; u₃ = 0

u₃ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₃ + v₄ = 1; 0 + v₄ = 1; v₄ = 1

	v1=2	v2=1	v3=4	v4=1
u1=0	3	1 [10]	3	4
u2=-2	5	3	2 [15]	3
u3=0	2 [5]	3	4 [0]	1 [20]
u4=1	6	2 [5]	5 [5]	3

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

(1; 3): 0 + 4 > 3; ?₁₃ = 0 + 4 - 3 = 1

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

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

	1	2	3	4	Запасы
1	3	1 [10] [-]	3 [+]	4	10
2	5	3	2 [15]	3	15
3	2 [5]	3	4 [0]	1 [20]	25
4	6	2 [5] [+]	5 [5] [-]	3	10
Потребности	5	15	20	20

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

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

	1	2	3	4	Запасы
1	3	1 [5]	3 [5]	4	10
2	5	3	2 [15]	3	15
3	2 [5]	3	4 [0]	1 [20]	25
4	6	2 [10]	5	3	10
Потребности	5	15	20	20

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

u₁ + v₂ = 1; 0 + v₂ = 1; v₂ = 1

u₄ + v₂ = 2; 1 + u₄ = 2; u₄ = 1

u₁ + v₃ = 3; 0 + v₃ = 3; v₃ = 3

u₂ + v₃ = 2; 3 + u₂ = 2; u₂ = -1

u₃ + v₃ = 4; 3 + u₃ = 4; u₃ = 1

u₃ + v₁ = 2; 1 + v₁ = 2; v₁ = 1

u₃ + v₄ = 1; 1 + v₄ = 1; v₄ = 0

	v1=1	v2=1	v3=3	v4=0
u1=0	3	1 [5]	3 [5]	4
u2=-1	5	3	2 [15]	3
u3=1	2 [5]	3	4 [0]	1 [20]
u4=1	6	2 [10]	5	3

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij. Минимальные затраты составят: Z= 1*5 + 3*5 + 2*15 + 2*5 + 1*20 + 2*10 = 100.

Заключение

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

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

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

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

1. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.

2. Баумоль У. Экономическая теория и исследование операций. - М.; Наука, 2004.

3. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.

4. Боровков А.А. Математическая статистика. М.: Наука, 2004.

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