Введение

Общая транспортная задача

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

Метод решения транспортной задачи

Практическая часть

Введение

Из истории линейного программирования

Система линейных неравенств изучалась в математике давно. Первый способ их решения - метод исключения неизвестных - был предложен Ж.Фурье еще в 20-х годах прошлого столетия.

Ж.Фурье также описал в геометрической форме метод решения оптимизационной задачи линейного программирования, которые через 100 с лишним лет стал широко применяться на практике и получил название симплекс-метода. Вслед за Фурье изучением систем линейных неравенств в связи с их приложениями в механике занимался в середине и в конце прошлого века М.В. Остроградский и Г.Фаркаш.

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

Первооткрывательские работы в этой области были выполнены в СССР Л.В. Конторовичем, предложившим и рассчитавшим в конце 30-х годов ряд линейных оптимизационных моделей планирования производства. В послевоенные годы активные исследования по линейным неравенствам развернулось в США, где в 1948 году по предложению Т.Купманса и появился сам термин "линейное программирование".

Первоначально общая математическая задача линейного программирования была поставлена в 1947 году Данцингом, который предложил для ее решения та называемый симплексный метод. Некоторые задачи, связанные с определением экстремума линейной формы на переменные которой положены линейные ограничения, были сформулированы еще раньше. Такими задачами, например, являются транспортная задача, выдвинутая Хичкоком (1941 г.) и независимо от него Купмансом, и задача о диете Стиглера (1945г).

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

Одной из первых проблем, для исследования которых были с успехом применены методы линейного программирования, явилась транспортная задача. Поставленная первоначально Ф.Л.Хичкоком , транспортная задача позднее была детально разобрана Т.С.Купмасом. Формулировка ее как задачи линейного программирования и методы решения впервые были даны Ж.Б.Данцигом. Предложенный им вычислительный процесс является детализацией симплексного метода применительно к транспортной задаче.

Примечаний нет.