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

СОДЕРЖАНИЕ
Dведение 3
1. Теоретическое обоснование выбора метода построения начального опорного плана транспортной задачи 5
1.1. Анализ методов решения задач оптимизации 5
1.2. Общая постановка задач оптимизации 8
1.3. Транспортная задача – специальная задача линейного программирования 9
1.4. Постановка транспортной задачи линейного программирования 10
1.5. Модели транспортной задачи линейного программирования 12
1.6. Опорный план транспортной задачи линейного программирования 13
1.7. Построение начального опорного плана транспортной задачи методом северо-западного угла 14
Выводы по главе 1 16
2. Практическое использование метода северо-западного угла для построения начального опорного плана транспортной задачи 17
2.1. Постановка задачи 17
2.2. Проверка необходимого и достаточного условия 17
2.3. Построение начального опорного плана транспортной задачи 17
2.4. Нахождение оптимального опорного плана транспортной задачи 24
Выводы по главе 2 26
Заключение 27
Список использованной литературы 28

Для этого построим начальный опорный план по методу минимального элемента.Суть данного метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Результат применения метода минимального элемента представлен в таблице 8.Построение начального опорного плана по методу минимального элемента1234Запасы1455[70]6[30]10022[50]1[100]83150373910[50]50Потребности501007080Число занятых клеток таблицы =5, а должно быть m + n - 1 = 6. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно: Искомый элемент равен 2 Для этого элемента запасы равны 150, потребности 50. Поскольку минимальным является 50, то вычитаем его. x21 = min(150,50) = 50. x5561002183150 - 50 = 100x39105050 - 50 = 010070800Искомый элемент равен 1 Для этого элемента запасы равны 100, потребности 100. Поскольку минимальным является 100, то вычитаем его. x22 = min(100,100) = 100. xx5610021xx100 - 100 = 0xx910500100 - 100 = 070800Искомый элемент равен 5 Для этого элемента запасы равны 100, потребности 70. Поскольку минимальным является 70, то вычитаем его. x13 = min(100,70) = 70. xx56100 - 70 = 3021xx0xxx10500070 - 70 = 0800Искомый элемент равен 6 Для этого элемента запасы равны 30, потребности 80. Поскольку минимальным является 30, то вычитаем его. x14 = min(30,80) = 30. xx5630 - 30 = 021xx0xxx105000080 - 30 = 500Искомый элемент равен 10 Для этого элемента запасы равны 50, потребности 50. Поскольку минимальным является 50, то вычитаем его. x34 = min(50,50) = 50. xx56021xx0xxx1050 - 50 = 000050 - 50 = 001234Запасы1455[70]6[30]10022[50]1[100]83150373910[50]50Потребности501007080Число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 6. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно: Искомый элемент равен 3 Для этого элемента запасы равны 150, потребности 80. Поскольку минимальным является 80, то вычитаем его. x24 = min(150,80) = 80. 455x1002183150 - 80 = 70739x50501007080 - 80 = 00Искомый элемент равен 1 Для этого элемента запасы равны 70, потребности 100. Поскольку минимальным является 70, то вычитаем его. x22 = min(70,100) = 70. 455x100x1x370 - 70 = 0739x5050100 - 70 = 307000Искомый элемент равен 3 Для этого элемента запасы равны 50, потребности 30. Поскольку минимальным является 30, то вычитаем его. x32 = min(50,30) = 30. 4x5x100x1x30739x50 - 30 = 205030 - 30 = 07000Искомый элемент равен 4 Для этого элемента запасы равны 100, потребности 50. Поскольку минимальным является 50, то вычитаем его. x11 = min(100,50) = 50. 4x5x100 - 50 = 50x1x30x39x2050 - 50 = 007000Искомый элемент равен 5 Для этого элемента запасы равны 50, потребности 70. Поскольку минимальным является 50, то вычитаем его. x13 = min(50,70) = 50. 4x5x50 - 50 = 0x1x30x39x200070 - 50 = 2000Искомый элемент равен 9 Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его. x33 = min(20,20) = 20. 4x5x0x1x30x39x20 - 20 = 00020 - 20 = 0001234Запасы14[50]55[50]6100221[70]83[80]150373[30]9[20]1050Потребности501007080В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Число занятых клеток таблицы=6. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: Несмотря на то, что построение начального опорного плана по методу минимального элемента получилось достаточно объемным, величина затрат на перевозки (значение целевой функции) имеет значительно меньший показатель, чем полученная при использовании метода северо-западного угла.Нахождение оптимального опорного плана транспортной задачиПроверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 4; 0 + v1 = 4; v1 = 4u1 + v3 = 5; 0 + v3 = 5; v3 = 5u3 + v3 = 9; 5 + u3 = 9; u3 = 4u3 + v2 = 3; 4 + v2 = 3; v2 = -1u2 + v2 = 1; -1 + u2 = 1; u2 = 2u2 + v4 = 3; 2 + v4 = 3; v4 = 1v1=4v2=-1v3=5v4=1u1=04[50]55[50]6u2=221[70]83[80]u3=473[30]9[20]10Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(2;1): 2 + 4 > 2; ∆21 = 2 + 4 - 2 = 4 (3;1): 4 + 4 > 7; ∆31 = 4 + 4 - 7 = 1 max(4,1) = 4 Выбираем максимальную оценку свободной клетки (2;1): 2 Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 1234Запасы14[50][-]55[50][+]610022[+]1[70][-]83[80]150373[30][+]9[20][-]1050Потребности501007080Цикл приведен в таблице (2,1 → 2,2 → 3,2 → 3,3 → 1,3 → 1,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 1234Запасы14[30]55[70]610022[20]1[50]83[80]150373[50]91050Потребности501007080Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 4; 0 + v1 = 4; v1 = 4u2 + v1 = 2; 4 + u2 = 2; u2 = -2u2 + v2 = 1; -2 + v2 = 1; v2 = 3u3 + v2 = 3; 3 + u3 = 3; u3 = 0u2 + v4 = 3; -2 + v4 = 3; v4 = 5u1 + v3 = 5; 0 + v3 = 5; v3 = 5v1=4v2=3v3=5v4=5u1=04[30]55[70]6u2=-22[20]1[50]83[80]u3=073[50]910Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят:Таким образом, из 1-го склада необходимо груз направить в 1-й магазин (30), в 3-й магазин (70).Из 2-го склада необходимо груз направить в 1-й магазин (20), в 2-й магазин (50), в 4-й магазин (80).Из 3-го склада необходимо весь груз направить в 2-й магазин.Выводы по главе 2В результате решения транспортной задачи построен начальный опорный план по методу северо-западного угла и методу минимального элемента.Величина перевозок по методу северо-западного ушла составила 1650 ед., а по методу минимального элемента 1030 ед.Таким образом, низкая эффективность метода северо-западного угла по сравнению с методом минимального элемента доказана.заключениеВ настоящее время большое количество технических задач требует поиска экстремума некоторой целевой функции на строго заданной области определения, то есть применяется условная оптимизация. Существующие методы решения оптимальных задач отличаются своей многогранностью и широким спектром применения. При этом эффективность выбранного метода в том или ином случае зависит от направления анализа предложено в задаче математической модели.В данном исследовании были изучены вопросы использования методов линейного программирования для нахождения оптимального плана перевозок транспортной задачи. В частности, был рассмотрены особенности метода северо-западного угла и его практическое применение для построения начального опорного плана транспортной задачи. В ходе решения практической задачи была доказана низкая эффективность данного метода.список использованной литературыБанди Б. Методы оптимизации // М.: Радио и связь, 1988.– 128 с.Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, Гл. ред. физ.-мат. лит., 2012.– 824 c. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985. 509 c. Математика в экономике. Математические методы и модели: учеб- ник / М. С. Красс, Б. П. Чупрынов. – М.: Финансы и статистика, 2011. – 544 с.: ил. Таха, Хемди А. Введение в исследование операций, 7-издание,: Пер. с англ. – М.: Издательский дом «Вильямс», 2010. – 912 с.: ил. – Парал. Тит. англ. Красс М. С., Чупрынов Б. П. Основы математики и её приложения в экономическом образовании: учебник. – 6-е изд., испр. – М.: Издательст- во “Дело” АНХ, 2012. – 720 с. Кремер Н. Ш., Путко Б. А., Тришин И. М. Математика для экономи- стов: от Арифметики до Эконометрики: учеб.-справоч. пособие / под. ред. проф. Н. Ш. Кремера. – М.: Высшее образование, 2012. – 646 с. – (Основы наук). Шикин Е. В, Чхартишвили А. Г. Математические методы и модели в управлении: Учеб. пособие. – 2-е изд,. Испрв, – М.: Дело, 2012, – 440 с. – (Сер. «Наука управления») Данко П. Е., Попов А. Г., Кожевникова Т. Я. Высшая математика в упражнениях и задачах. В 2-х ч. Ч I: Учеб. пособие для втузов. – 5-е изд., испр. – М.: Высш. шк. 2011. – 304 с.: ил. Партыка Т. Л., Попов И. И. Математические методы. – Учебник. – М.: ФОРУМ: ИНФРА-М, 2013. – 464 с. (Профессиональное образование). Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред. В. И. Ермакова. – М.: ИНФРА-М, 2011. – 575 с. (Серия «Высшее образование»).