Применение методов линейного программирования в военном деле. Симплекс-метод

Рефераты, курсовые, дипломные, контрольные (предпросмотр)

Тип: Реферат. Файл: Word (.doc) в архиве zip. Категория: Информатика, IT
Адрес этого реферата http://referat-kursovaya.repetitor.info/?essayId=24704 или
Загрузить
В режиме предпросмотра не отображаются таблицы, графики и иллюстрации. Для получения полной версии нажмите кнопку «Загрузить». Рефераты, контрольные, дипломные, курсовые работы предоставляются в ознакомительных целях, не для плагиата.
Страница 1 из 4 [Всего 4 записей]1 2 3 4 »

ЧТО ТАКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

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

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

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

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".

Эти премии получили свое название в честь их учредителя - известного химика и изобретателя Альфреда Нобеля, они должны были присуждаться за научные открытия в области физики, химии, физиологии или медицины, за литературные произведения, "отражающие человеческие идеалы", а так же тем, кто "внесет весомый вклад в сплочение народов, уничтожение рабства, снижение численности существующих армий и содействие мирной договоренности". Математикам премия не предназначалась. Однако в 1969 году Шведский банк по случаю 300-летия со дня своего образования учредил премию памяти А.Нобеля - по экономическим наукам. Она то и была присуждена в 1975 году Л.В.Канторовичу и Т.Купмансу за создание новой математической науки (получившей название линейного программирования) и применение этой теории в экономике.

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда... Поэтому простой перебор вершин не годился. Леонид Витальевич писал: "оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков... Это настойчиво побудило меня к поиску эффективного метода их решения". И уже летом 1939 года была сдана в набор книга Л.В.Канторовича "Математические методы организации и планирования производства", в которой закладывались основания того, что ныне называется математической экономикой.

Но вернемся в 1939 год. Говорят, что истина рождается ересью и увы, так случилось и с идеями Л.В.Канторовича в области экономики. Они не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана.

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

Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течении пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже не а экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем - словом, стоит ли принимать такую книжку во внимание... Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадим должное благородству американского ученого!

А самому Леониду Витальевичу - как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от "грехов" молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет и кое что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А начиная с 1960 года Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.

ОСНОВНЫЕ НАПРАВЛЕНИЯ ИСПОЛЬЗОВАНИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ВОЕННОМ ДЕЛЕ.

Наиболее распространенными направлениями использования линейного программирования в военном деле являются:

- задача о перевозках (транспортная задача)

- задача на распределение сил и средств (распределение сил и средств поражения по целям, распределение сил и средств разведки и др.)

ЗАДАЧИ О ПЕРЕВОЗКАХ (ТРАНСПОРТНАЯ ЗАДАЧА).

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

Сформулируем в общем виде транспортную задачу линейного программирования по критерию стоимости. Эта задача имеет значение тогда, когда время не является определяющим фактором при организации перевозок.

RSSСтраница 1 из 4 [Всего 4 записей]1 2 3 4 »


При любом использовании материалов сайта обязательна гиперссылка на сайт «Репетитор».
Разработка и Дизайн компании Awelan
www.megastock.ru
Проверить аттестат