Транспортная задача и ее применение

Введение
Задачи на наибольшие и наименьшие значения привлекали к себе внимание на протяжении всей истории математики. Античные геометры поставили и решили несколько задач на экстремумы, которые теперь называются изопериметрическими, например, среди плоских замкнутых кривых заданной длины найти кривую, охватывающую набольшую площадь (ответ - окружность).
До второй половины XVII столетия не существовало общих приемов решения задач на экстремум. Первый общий рецепт, с помощью которого предлагалось исследовать задачи на максимум и минимум, был описан П. Ферма (около 1630 г.). На современном языке он звучит так: в точке экстремума (некоторой функции одного переменного) производная равна нулю, и потому экстремумы следует искать среди корней производных. Этот результат входит сейчас в школьный курс математики под названием теоремы Ферма. На самом же деле Ферма описал этот прием фактически лишь для многочленов. В общем виде он был впервые получен Ньютоном (в шестидесятые годы XVII столетия), а затем переоткрыт Лейбницем и впервые опубликован им в знаменитой статье, с которой начинается история математического анализа: «Новый метод нахождения наибольших и наименьших величин...».
В XVIII в. усилиями Эйлера и Лагранжа были созданы приемы решения экстремальных задач с функциями от нескольких переменных без ограничений и с ограничениями типа равенств. Основной прием — метод множителей Лагранжа — сейчас входит в программу любого математического и технического вуза. Уже в наши дни эти исследования были дополнены исследованием задач, где ограничения задаются равенствами и неравенствами. Весь этот цикл вопросов получил название математического программирования.
К началу XX в. многие считали, что проблематика теории задач на экстремум практически исчерпана. Но оказалось, что это не так. В 1939 г. к заведующему отделом Института математики и механики при Ленинградском университете профессору Л. В. Канторовичу пришли на консультацию представители фанерного треста и предложили его вниманию несколько задач, возникших у них на производстве. При математической формализации выяснилось, что они сводятся к нахождению экстремума линейных функций на многогранниках. Перебрать все вершины многогранников не представлялось возможным из-за огромного их числа Л. В. Канторович нашел иные пути решения и исследования таких задач. Этим он заложил основы нового направления в теории экстремальных задач. Оно получило название линейного программирования. Методы линейного программирования нашли широчайшее применение на практике, в основном в экономике. За разработку математических методов и их внедрение в экономику Л. В. Канторовичу в 1965 г. была присуждена Ленинская, а в 1975 (совместно с американским экономистом Т. Ч. Купмансом) — Нобелевская премия.
Усложнение современной экономической практики привело к необходимости широчайшего внедрения методов нахождения оптимальных решений, а, следовательно, и вычислительной техники в повседневную работу инженеров и экономистов. Одним из главных направлений развития общества в наше время становится совершенствование различных видов целенаправленной деятельности человека. Обычно та или иная цель деятельности может быть достигнута разными путями, но всегда полезно знать лучший из них, так как в реальных условиях приходится считаться с ограниченностью материальных ресурсов и времени, расходуемых на достижение цели. Понятие «лучший» относительно: оно начинает что-либо означать тогда, когда назван показатель (критерий) качества принимаемых решений.
Роль критерия качества этим не исчерпывается. Как правило, представляет интерес его количественная оценка. Если она существует, появляется возможность построить математическую модель изучаемой системы и определить тем самым характер связи принятого критерия с параметрами исследуемых объектов.
Несмотря на разнообразие подобных экстремальных задач, все они с формальной точки зрения сводятся к одной общей постановке: у объекта выделяются переменные величины x=(x1, x2, ..., xn),, влияющие на его поведение (развитие), вводится функционал от этих переменныхF(x1, x2, ..., xn),значение которого характеризует качество поведения объекта. Возможно, переменные являются свободными, то есть на них не накладывается никаких ограничений, но чаще объект действует в ограниченных условиях, и это находит отражение в условиях на переменные в виде уравнений или неравенств: g(x1, x2, ..., xn)=0 или g(x1, x2, ..., xn)≤0.
Многие задачи прикладной математики, да и классической математики, являются задачами поиска экстремума. В математике накоплен огромный арсенал методов их решения, в котором различаются аналитические и численные методы. Аналитическое методы основаны на классических результатах математического анализа, численные чаще всего требуют использования вычислительной техники, всегда наиболее мощной, самой современной, с использованием изощренных методов программирования.
В теории линейного программирования все функции-ограничения, а также сам функционал – целевая функция являются линейными по всем переменным. К настоящему времени накоплен огромный арсенал методов линейного программирования, мощных алгоритмов, решено множество сложных задач. Однако одним из самых популярных методов линейного программирования (во всяком случае – самым известным) является симплекс-метод, который был предложен американцем-математиком Дж. Данцигом в 1951 г. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.
Транспортная задача относится к перечню классических задач, решаемых в практике деятельности людей. Однако транспортная задача может рассматриваться и как задача линейного программирования со специальной матрицей ограничений. Построенные для таких задач специальные методы (например, метод потенциалов) более эффективны, чем общий симплекс-метод, и допускают обобщение на более широкие задачи.
Объект нашего исследования: транспортные задачи как задачи линейного программирования.
Предмет исследования: методы и приемы решения транспортных задач как задач линейного программирования.
Цель исследования: систематизация методов и приемов решения задач линейного программирования и применение для этого метода потенциалов.

Список литературы.
1. Акулич И.Л. Математическое программирование в примерах и
задачах. - М.; Высшая школа. 1993. - 335 с.
2. Аттетков А.В., Гаткин С.В., Зарубин B.C. Методы оптимизации - М.;
Издательство МГТУ им. Н.Э. Баумана, 2004. - 432 с
3. Васильев В.П. Численные методы решения экстремальных задач. - М.:
Наука. 1980.-518 с.
4. Габбасов Р., Кириллова Ф.М. Методы оптимизации. - Минск: Изд-во
БГУ, 1981.
5. Галеев Э.М., Тихомиров В.М. Краткий курс теории экстремальных
задач. – М.: Изд-во Моск. ун-та, 1989. – 204 с.
6. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах н
задачах. - М.; Высшая школа. 2005. - 544 с.
7. Романовский И.В. Алгоритмы решения экстремальных задач. –
Главная ред. Физ-мат лит-ры, изд-во «Наука», М., 1977. - 352 с.
8. Калихман П. Сборник задач по математическому программированию.
Изд. 2-е доп. и перераб. М.. «Высш. школа». 1975. 270 с.
9. Схрейвер А. Теория линейного н целочисленного программирования:
В 2-х т. Т. 1: Пер. с англ. - М.: Мир, 1991. - 360 с.
10. Смирнов И. А. Методы оптимизации. Базовый курс : учеб. пособие /
И. А. Смирнов. – СПб. : СПбГТИ(ТУ), 2010. – 101 с.