Оптимизационные задачи линейного программирования

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

ВВЕДЕНИЕ

В данной курсовой работе рассматриваются такие темы, как 1) оптимизационные задачи линейного программирования, 2) элементы теории графов, 3) задача о ранце и 4) транспортная задача.

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

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

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

2) Граф - это система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий. Кружки - вершины графа. Линию со стрелками называют дугами, без стрелок - ребра.

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

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

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

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

Целью данной курсовой работы является:

Решение задач симплекс-методом.

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

Решение задачи о ранце

Решение транспортной задачи методом северо-западного угла, методом минимального элемента и методом потенциалов.



1. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

количество продукции - расход сырья;

количество продукции - качество продукции.

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

При постановке задачи оптимизации необходимо:

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

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

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

4. Учет ограничений.

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

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

1.1 Лабораторная работа №1

Предприятие для изготовления различных изделий А, В и С использует 3 вида сырья. Нормы расхода сырья каждого вида на производстве единицы продукции данного вида и цена приведены в таблице. Изделия А, В и С могут производиться в любых соотношения. Однако производство ограничено имеющимся в распоряжении предприятия сырьем 1-го вида в количестве 230, 2-го вида - 280, 3 вида - 330.

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



Таблица 1

Вид сырья	Нормы затрат сырья (кг) на производство ед. продукции
	А	В	С
230	26	22	16
280	13	12	15
330	14	11	13
Цена единицы продукции	16	14	20

Составим математическую модель задачи. Искомый выпуск изделий А обозначим , изделий В - через , изделий С - . Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные , и должны удовлетворять следующей системе неравенств:

Общая стоимость произведенной предприятием продукции при условии выпуска изделий А, изделий В и изделий С.

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



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

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

Преобразованную систему уравнений запишем в векторной форме:

Поскольку среди векторов имеются три единичных вектор, для данной задачи можно непосредственно записать опорный план. Таковым является X=(0, 0, 0, 230, 280, 330), определяемый системой трехмерных единичных векторов , которые образуют базис трехмерного пространства.

Составим симплексную таблицу первой итерации:

Таблица 2

i	базис	С		16	14	20	0	0	0
1		0	230	26	16	12	1	0	0
2		0	280	13	12	15	0	1	0
3		0	330	14	11	13	0	0	1
4			0	-16	-14	-20	0	0	0

Так как данный план не является оптимальным, поскольку нижняя строка симплексной таблицы содержит отрицательные числа. В этом случае столбец вектора 2-ая строка являются направляющими. Составляем таблицу второй итерации:

Таблица 3

i	базис	С		16	14	20	0	0	0
1		0	6,8	15,6	6,4	0	1	-0,86	0
2		20	18,6	0,86	0,8	1	0	0,06	0
3		0	88,2	2,7	0,6	0	0	-0,86	1
4			372	1,3	2	0	0	1,3	0

Данный план является оптимальным

X= (0; 0; 18,6; 6,8; 0; 88,2)

Очевидно, что оптимальный план производства изделий А, В, С является план, согласно которому производится 18,6 изделий вида С. Общая стоимость изготавливаемой продукции равна 372.

Установим теперь возможные границы изменения цен каждого из изделий, внутри которых найденный max оптимизированного производства. Предположим, что цена изделия вида А =16+, где . Требуется найти такие значения параметра , что для найденного плана

= (0, 0, 18,6) достигается максимальное значение



i	Базис	С		16+	14	20	0	0	0
1		0	6,8	15,6	6,4	0	1	-0,8	0
2		20	18,6	0,86	0,8	1	0	0,06	0
3		0	88,2	2,7	0,6	0	0	-0,86	1
4			372	1,3-	2	0	0	1,3	0

План = (0, 0, 18,6) является оптимальным для построенной задачи параметрического программирования, если 1,3-. Тогда , это означает, что , то задача имеет оптимальный план = (0, 0, 18,6), т. е. предприятию нецелесообразно включать в план производства продукции выпуск изделий вида А, при условии, что цена 1-го такого изделия не превышает 17,3.

1.2 Лабораторная работа №2

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

Таблица 1

Вид сырья	Нормы затрат сырья (кг) на производство ед. продукции
	А	В	С
130	8	6	5
150	7	5	7
180	5	6	9
Цена реализации	14	18	17

Составим математическую модель задачи. Искомый выпуск изделий А обозначим , изделий В - через , изделий С - . Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные , и должны удовлетворять следующей системе неравенств:

Общая стоимость произведенной предприятием продукции при условии выпуска изделий А, изделий В и изделий С.

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

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

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

Преобразованную систему уравнений запишем в векторной форме:

Поскольку среди векторов имеются три единичных вектор, для данной задачи можно непосредственно записать опорный план. Таковым является X=(0, 0, 0, 130, 150, 180), определяемый системой трехмерных единичных векторов , которые образуют базис трехмерного пространства.

Составим симплексную таблицу.

Таблица 2

i	Базис	С		14	18	17	0	0	0
1		0	130	8	6	5	1	0	0
2		0	150	7	5	7	0	1	0
3		0	180	5	6	9	0	0	1
4			0	-14	-18	-17	0	0	0
1		18	21,7	1,3	1	0,8	0,17	0	0
2		0	41,5	0,3	0	2,8	-0,8	1	0
3		0	49,8	-3	0	4	-1	0	1
4			390,6	10	0	-2	3	0	0
1		18	11,47	1,9	1	0	0,4	0	-0,2
2		0	6,64	2,4	0	0	-0,1	1	-0,7
3		17	12,45	-0,75	0	1	-0,25	0	0,25
4			418	8,5	0	0	2,5	0	0,5

Данный план является оптимальным

X= (0; 11, 47; 12, 45; 0; 6, 64; 0)

= 418

Из таблицы 2 видно, что при оптимальном плане производства, изделий должно быть изготовлено 11,47 изделий вида А, 6, 64 изделий вида В и 12,45 изделий вида С.

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

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



, , =

Найденный вектор определяет оптимальный план (0;0,4+16;-0,25+12,5;0;-0,1+24;0) или



2. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).

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

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

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

Путь в графе (иногда говорят простой путь) - это маршрут без повторения вершин (а значит, и ребер).

Длина пути - это число дуг пути или сумма длин его дуг, если длины заданы

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

Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). 

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

Эйлеровы и полуэйлеровы графы.

Именно с задач, поставленных и решенных в этом разделе, началась теория графов. Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз. Наш петербургский знаменитый математик швейцарского происхождения Леонард Эйлер блестяще решил эту задачу. В соответствии с поставленной Кантом (и решенной Эйлером) задачей можно дать следующие определения:

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

2.1 Графы с правильной нумерацией

Задача о кратчайшем пути.

Пусть задана сеть из вершин, т. е. ориентированный граф, в котором выделяем 2 вершины. Вход - 0 вершина и выход - вершина. Задача заключается в поиске кратчайшего пути от входа к выходу.

Алгоритм для нахождения кратчайшего пути с правильной нумерацией вершин

Шаг 1. Пометим нулевую вершину индексом

Шаг 2. Пометим вершину индексом . Индекс выхода равен длине кратчайшего пути. Когда индексы устанавливаются, кратчайший путь определяется методом обратного хода от выхода к входу.

Кратчайшим является путь такой, что

 

2.2 Графы с произвольной нумерацией

Рассмотрим графы с произвольной нумерацией.

Шаг 1. Пометим нулевую вершину индексом . Все остальные вершины индексами , где

Шаг 2. Рассмотрим все дуги. Для дуги (i; j), если , то вычисляем новое значение.

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

Графы с произвольной нумерацией

1 дуга (0;1)

;

2 дуга (0;3)

3 дуга (1;2)

4 дуга (3;4)



5 дуга (4;1)

6 дуга (4;5)

7 дуга (2;6)

8 дуга (5;6)

9 дуга (5;7)

10 дуга (7;8)

11 дуга (8;9)

12 дуга (9;10)

13 дуга (6;9)

14 дуга (9;10)

Длина пути равна 11



1 дуга (0;1)

2 дуга (0;2)

3 дуга (0;3)

4 дуга (1;5)

5 дуга (2;4)

6 дуга (3;4)

7 дуга (4;5)



8 дуга (4;6)

9 дуга (5;6)

10 дуга (6;7)

11 дуга (6;9)

12 дуга (7;8)

13 дуга (8;9)

14 дуга (9;10)

Длина пути равна 17



1 дуга (0;1)

2 дуга (0;2)

3 дуга (1;5)

4 дуга (2;3)

5 дуга (5;4)

6 дуга (5;7)

7 дуга (4;7)

8 дуга (7;8)

9 дуга (3;6)

10 дуга (6;8)

11 дуга (8;9)

12 дуга (9;10)



Длина пути равна 27

1 дуга (0;1)

2 дуга (0;3)

3 дуга (3;1)

4 дуга (3;5)

5 дуга (5;6)

6 дуга (1;2)

7 дуга (2;4)



8 дуга (4;6)

9 дуга (6;7)

10 дуга (7;8)

11 дуга (8;9)

12 дуга (6;9)

13 дуга (9;10)

Длина пути равна 14



1 дуга (0;1)

2 дуга (1;2)

3 дуга (2;3)

4 дуга (2;5)

5 дуга (3;4)

6 дуга (5;4)

7 дуга (5;6)

8 дуга (4;7)

9 дуга (7;8)

10 дуга (8;9)

11 дуга (9;10)

12 дуга (5;6)



13 дуга (6;10)

Длина пути равна 14

2.3 Задача о кратчайшем маршруте

Алгоритм решения задачи:

Шаг 1. Рассмотрим сеть с выделенным узлом 1, все узлы, соединённые с ним одним ребром, пометим первое число меткой 2,1(1е число это расстояние от вершины 1, 2е число номер первого узла) у вершины 2 метка 2,1,у числа 2 метка постоянна, при помещении постоянной метки выделяем узел 2 как узел 1.

Шаг 2. Отбираются все узлы, которые соединены с узлом 2 одним ребром и не имеют постоянной метки - это узел 7, который помечаем постоянной меткой 7,2, узел 8 отмечаем меткой 9,7, отбираем ребра соединенные с узлом 8, сравниваем длину маршрута 1-2-7-8 и длину маршрута 1-3-4-7-8 и длину маршрута 1-3-5-6-8, видим, что длина 1-2-7-8 равна 9, а 1-2-4-7-8 равна 16, маршрута 1-2-5-6-8 равна 20, следовательно метка узла 2 остается постоянной.

Шаг 3. Отбираются все узлы, соединенные с узлом 7, узлу 9 присваиваем метку 13,7

Шаг 4. Сравниваем длины маршрутов 1-2-7-9-10 и 1-2-7-8-10,длина 1го равна 16, 2го 14, следовательно узел 10 получает постоянную метку 14,8

Узел	Маршрут	Длина
2	1-3	3
3	1-2	2
4	1-3-4	9
5	1-3-5	10
6	1-3-5-6	18
7	1-2-7	7
8	1-2-7-8	9
9	1-2-7-9	13
10	1-2-7-8-10	14



3. ЗАДАЧА О РАНЦЕ

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

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

max

R

Пусть имеется 7 предметов, веса и полезности которых указаны в таблице

R=14

Таблица 3.1

i
1	3	4
2	4	3
3	4	5
4	3	2
5	3	5
6	2	4
7	3	3



Набор предметов, обладающий максимальной суммарной полезностью и удовлетворяющий ограничению:1,4,5,6,7.=18



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

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

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

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

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

F = ??cijxij, (1)

при условиях:

?xij = ai, i = 1,2,…, m, (2)

?xij = bj, j = 1,2,…, n, (3)



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

	1	2	3	4	Запасы
1	5	2	1	0	90
2	2	4	3	6	40
3	1	3	4	2	70
Потребности	85	37	40	38

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

?a = 90 + 40 + 70 = 200

?b = 85 + 37 + 40 + 38 = 200

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

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

	1	2	3	4	Запасы
1	5	2	1	0	90
2	2	4	3	6	40
3	1	3	4	2	70
Потребности	85	37	40	38

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

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

План начинается заполняться с верхнего левого угла.

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

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

x11 = min(90,85) = 85.

5	2	1	0	90 - 85 = 5
x	4	3	6	40
x	3	4	2	70
85 - 85 = 0	37	40	38	0

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

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

x12 = min(5,37) = 5.

5	2	x	x	5 - 5 = 0
x	4	3	6	40
x	3	4	2	70
0	37 - 5 = 32	40	38	0

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

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

x22 = min(40,32) = 32.

5	2	X	x	0
x	4	3	6	40 - 32 = 8
x	x	4	2	70
0	32 - 32 = 0	40	38	0



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

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

x23 = min(8,40) = 8.

5	2	X	x	0
x	4	3	x	8 - 8 = 0
x	x	4	2	70
0	0	40 - 8 = 32	38	0

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

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

x33 = min(70,32) = 32.

5	2	X	x	0
x	4	3	x	0
x	x	4	2	70 - 32 = 38
0	0	32 - 32 = 0	38	0

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

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

x34 = min(38,38) = 38.

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



	1	2	3	4	Запасы
1	5[85]	2[5]	1	0	90
2	2	4[32]	3[8]	6	40
3	1	3	4[32]	2[38]	70
Потребности	85	37	40	38

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

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

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

F(x) = 5*85 + 2*5 + 4*32 + 3*8 + 4*32 + 2*38 = 791

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u2 + v2 = 4; 2 + u2 = 4; u2 = 2

u2 + v3 = 3; 2 + v3 = 3; v3 = 1

u3 + v3 = 4; 1 + u3 = 4; u3 = 3

u3 + v4 = 2; 3 + v4 = 2; v4 = -1

	v1=5	v2=2	v3=1	v4=-1
u1=0	5[85]	2[5]	1	0
u2=2	2	4[32]	3[8]	6
u3=3	1	3	4[32]	2[38]

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

(2;1): 2 + 5 > 2; ?21 = 2 + 5 - 2 = 5

(3;1): 3 + 5 > 1; ?31 = 3 + 5 - 1 = 7

(3;2): 3 + 2 > 3; ?32 = 3 + 2 - 3 = 2

max(5,7,2) = 7

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

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

	1	2	3	4	Запасы
1	5[85][-]	2[5][+]	1	0	90
2	2	4[32][-]	3[8][+]	6	40
3	1[+]	3	4[32][-]	2[38]	70
Потребности	85	37	40	38

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

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

	1	2	3	4	Запасы
1	5[53]	2[37]	1	0	90
2	2	4[0]	3[40]	6	40
3	1[32]	3	4	2[38]	70
Потребности	85	37	40	38

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u3 + v1 = 1; 5 + u3 = 1; u3 = -4

u3 + v4 = 2; -4 + v4 = 2; v4 = 6

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u2 + v2 = 4; 2 + u2 = 4; u2 = 2

u2 + v3 = 3; 2 + v3 = 3; v3 = 1

	v1=5	v2=2	v3=1	v4=6
u1=0	5[53]	2[37]	1	0
u2=2	2	4[0]	3[40]	6
u3=-4	1[32]	3	4	2[38]

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

(1;4): 0 + 6 > 0; ?14 = 0 + 6 - 0 = 6

(2;1): 2 + 5 > 2; ?21 = 2 + 5 - 2 = 5

(2;4): 2 + 6 > 6; ?24 = 2 + 6 - 6 = 2

max(6,5,2) = 6

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

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

	1	2	3	4	Запасы
1	5[53][-]	2[37]	1	0[+]	90
2	2	4[0]	3[40]	6	40
3	1[32][+]	3	4	2[38][-]	70
Потребности	85	37	40	38

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

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

	1	2	3	4	Запасы
1	5[15]	2[37]	1	0[38]	90
2	2	4[0]	3[40]	6	40
3	1[70]	3	4	2	70
Потребности	85	37	40	38

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u3 + v1 = 1; 5 + u3 = 1; u3 = -4

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u2 + v2 = 4; 2 + u2 = 4; u2 = 2

u2 + v3 = 3; 2 + v3 = 3; v3 = 1

u1 + v4 = 0; 0 + v4 = 0; v4 = 0

	v1=5	v2=2	v3=1	v4=0
u1=0	5[15]	2[37]	1	0[38]
u2=2	2	4[0]	3[40]	6
u3=-4	1[70]	3	4	2

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

(2;1): 2 + 5 > 2; ?21 = 2 + 5 - 2 = 5

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

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

	1	2	3	4	Запасы
1	5[15][-]	2[37][+]	1	0[38]	90
2	2[+]	4[0][-]	3[40]	6	40
3	1[70]	3	4	2	70
Потребности	85	37	40	38

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

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

	1	2	3	4	Запасы
1	5[15]	2[37]	1	0[38]	90
2	2[0]	4	3[40]	6	40
3	1[70]	3	4	2	70
Потребности	85	37	40	38



Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u2 + v1 = 2; 5 + u2 = 2; u2 = -3

u2 + v3 = 3; -3 + v3 = 3; v3 = 6

u3 + v1 = 1; 5 + u3 = 1; u3 = -4

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u1 + v4 = 0; 0 + v4 = 0; v4 = 0

	v1=5	v2=2	v3=6	v4=0
u1=0	5[15]	2[37]	1	0[38]
u2=-3	2[0]	4	3[40]	6
u3=-4	1[70]	3	4	2

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

(1;3): 0 + 6 > 1; ?13 = 0 + 6 - 1 = 5

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

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

	1	2	3	4	Запасы
1	5[15][-]	2[37]	1[+]	0[38]	90
2	2[0][+]	4	3[40][-]	6	40
3	1[70]	3	4	2	70
Потребности	85	37	40	38



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

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

	1	2	3	4	Запасы
1	5	2[37]	1[15]	0[38]	90
2	2[15]	4	3[25]	6	40
3	1[70]	3	4	2	70
Потребности	85	37	40	38

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u1 + v3 = 1; 0 + v3 = 1; v3 = 1

u2 + v3 = 3; 1 + u2 = 3; u2 = 2

u2 + v1 = 2; 2 + v1 = 2; v1 = 0

u3 + v1 = 1; 0 + u3 = 1; u3 = 1

u1 + v4 = 0; 0 + v4 = 0; v4 = 0

	v1=0	v2=2	v3=1	v4=0
u1=0	5	2[37]	1[15]	0[38]
u2=2	2[15]	4	3[25]	6
u3=1	1[70]	3	4	2

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.



Минимальные затраты составят:

F(x) = 2*37 + 1*15 + 0*38 + 2*15 + 3*25 + 1*70 = 264

производственный программа транспортный задача

4.2 Метод минимального элемента

Алгоритм:1. Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают меньшее из чисел. 2. Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются. 3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена. Математическая модель транспортной задачи:

F = ??cijxij, (1)

?xij = ai, i = 1,2,…, m, (2)

?xij = bj, j = 1,2,…, n, (3)

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

	1	2	3	4	Запасы
1	5	2	1	0	90
2	2	4	3	6	40
3	1	3	4	2	70
Потребности	85	37	40	38



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

?a = 90 + 40 + 70 = 200

?b = 85 + 37 + 40 + 38 = 200

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

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

	1	2	3	4	Запасы
1	5	2	1	0	90
2	2	4	3	6	40
3	1	3	4	2	70
Потребности	85	37	40	38

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

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

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

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

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

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

x14 = min(90,38) = 38.

5	2	1	0	90 - 38 = 52
2	4	3	x	40
1	3	4	x	70
85	37	40	38 - 38 = 0	0

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

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

x13 = min(52,40) = 40.

5	2	1	0	52 - 40 = 12
2	4	X	x	40
1	3	X	x	70
85	37	40 - 40 = 0	0	0

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

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

x31 = min(70,85) = 70.

5	2	1	0	12
2	4	X	x	40
1	x	X	x	70 - 70 = 0
85 - 70 = 15	37	0	0	0

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

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

x12 = min(12,37) = 12.

x	2	1	0	12 - 12 = 0
2	4	X	x	40
1	x	X	x	0
15	37 - 12 = 25	0	0	0

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

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

x21 = min(40,15) = 15.

x	2	1	0	0
2	4	X	x	40 - 15 = 25
1	x	X	x	0
15 - 15 = 0	25	0	0	0

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

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



x22 = min(25,25) = 25.

x	2	1	0	0
2	4	x	x	25 - 25 = 0
1	x	x	x	0
0	25 - 25 = 0	0	0	0

	1	2	3	4	Запасы
1	5	2[12]	1[40]	0[38]	90
2	2[15]	4[25]	3	6	40
3	1[70]	3	4	2	70
Потребности	85	37	40	38

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

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

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

F(x) = 2*12 + 1*40 + 0*38 + 2*15 + 4*25 + 1*70 = 264



ЗАКЛЮЧЕНИЕ

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

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

В ходе данной работы, мною были рассмотрены:

* основные понятия теории графов;

* симплекс метода;

* задача о планировании производств;

* методы решения транспортной задачи.

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



ЛИТЕРАТУРА

1. Баркалов С.А., Бурков В.Н., Новиков Д.А., Шульженко Н.А. Модели и механизмы в управлении организационными системами. М.: Издательство «Тульский полиграфист», 2003. Том 1. - 560 с., Том 2 - 380 с., Том 3 - 205 с. 2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. - 384 с.

3. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. - М.: Изд-во МАИ, 1998.

4. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. - М.: Высш. шк., 2002.

5. Смородинский С.С., Батин Н.В. Анализ и оптимизация систем на основе аналитических моделей. - Мн.: БГУИР, 1997.

6. Щетинин Е.Ю. Математические методы оптимизации. Конспект лекций.

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