Применение методов линейного программирования в военном деле. Симплекс-метод
Другие рефераты
РЕФЕРАТ
Тема: «Применение методов линейного программирования в
военном деле. Симплекс-метод»
курсанта 2-го курса I взв. 8-й роты
Дальневосточного военного института
им. К.К. Рокоссовского
Верещак Дмитрия Владимировича
ПЛАН
I. Что такое линейное программирование
II. Основные направления использования линейного программирования
в военном деле
1.Задачи о перевозках (транспортная) задача
2.Задачи оптимального распределения средств
поражения
III. Симплекс-метод
IV. Заключение
I.ЧТО ТАКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Каждый человек ежедневно, не всегда осознавая это решает проблему:
как получить наибольший эффект, обладая ограниченными средствами.
Наши средства и ресурсы всегда ограничены. Жизнь была бы менее
интересной , если бы это было не так. Не трудно выиграть сражение, имея
армию в 10 раз большую, чем у противника; Ганнибалу, чтобы разбить римлян
при Каннах, командуя вдвое меньшей армией, нужно было действовать очень
обдуманно.
Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо
составить план, или программу действий. Раньше план в таких случаях
составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX
века был создан специальный математический аппарат, помогающий это делать
«по науке». Соответствующий раздел математики называется математическим
программированием. Слово «программирование» здесь и в аналогичных терминах
(«линейное программирование, динамическое программирование» и т.п.) обязано
отчасти историческому недоразумению, отчасти неточному переводу с
английского. По-русски лучше было бы употребить слово «планирование». С
программированием для ЭВМ математическое программирование имеет лишь то
общее, что большинство возникающих на практике задач математического
программирования слишком громоздки для ручного счета, решить их можно
только с помощью ЭВМ, предварительно составив программу.
Временем рождения линейного программирования принято считать
1939г., когда была напечатана брошюра Леонида Витальевича Канторовича
«Математические методы организации и планирования производства». Поскольку
методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета,
а быстродействующих вычислительных машин в то время не существовало, работа
Л.В.Канторовича осталась почти не замеченной.
Свое второе рождение линейное программирование получило в начале
пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение
линейным программированием, вызвавшее в свою очередь развитие других
разделов математического программирования. В 1975 году академик
Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию
по экономическим наукам за «вклад в разработку теории и оптимального
использования ресурсов в экономике».
Эти премии получили свое название в честь их учредителя –
известного химика и изобретателя Альфреда Нобеля, они должны были
присуждаться за научные открытия в области физики, химии, физиологии или
медицины, за литературные произведения, «отражающие человеческие идеалы», а
так же тем, кто «внесет весомый вклад в сплочение народов, уничтожение
рабства, снижение численности существующих армий и содействие мирной
договоренности». Математикам премия не предназначалась. Однако в 1969 году
Шведский банк по случаю 300-летия со дня своего образования учредил премию
памяти А.Нобеля – по экономическим наукам. Она то и была присуждена в 1975
году Л.В.Канторовичу и Т.Купмансу за создание новой математической науки
(получившей название линейного программирования) и применение этой теории в
экономике.
В автобиографии, представленной в Нобелевский комитет, Леонид
Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К
нему, 26-летнему профессору-математику, обратились за консультацией
сотрудники лаборатории планерного треста, которым нужно было решить задачу
о наиболее выгодном распределении материала между станками. Эта задача
сводилась к нахождению максимума линейной функции, заданной на
многограннике. Максимум такой функции достигался в вершине, однако число
вершин в этой задаче достигало миллиарда… Поэтому простой перебор вершин не
годился. Леонид Витальевич писал: «оказалось, что эта задача не является
случайной. Я обнаружил большое число разнообразных по содержанию задач,
имеющих аналогичный математический характер: наилучшее использование
посевных площадей, выбор загрузки оборудования, рациональный раскрой
материала, распределение транспортных грузопотоков… Это настойчиво побудило
меня к поиску эффективного метода их решения». И уже летом 1939 года была
сдана в набор книга Л.В.Канторовича «Математические методы организации и
планирования производства», в которой закладывались основания того, что
ныне называется математической экономикой.
Но вернемся в 1939 год. Говорят, что истина рождается ересью и увы,
так случилось и с идеями Л.В.Канторовича в области экономики. Они не
встретили понимания в момент их зарождения, были объявлены ересью, и его
работа была прервана.
Концепции Леонида Витальевича вскоре после войны были переоткрыты
на западе. Американский экономист Т.Купманс в течении многих лет привлекал
внимание математиков к ряду задач, связанных с военной тематикой. Он
активно способствовал тому, чтобы был организован математический коллектив
для разработки этих проблем. В итоге было осознано, что надо научиться
решать задачи о нахождении экстремумов линейных функций на многогранниках,
задаваемых линейными неравенствами. По предложению Купманса этот раздел
математики получил название линейного программирования.
Американский математик А.Данциг в 1947 году разработал весьма
эффективный конкретный метод численного решения задач линейного
программирования (он получил название симплекс метода). Идеи линейного
программирования в течении пяти шести лет получили грандиозное
распространение в мире, и имена Купманса и Данцига стали повсюду широко
известны.
Примерно в это время Купманс узнал, что еще до войны в далекой
России уже было сделано нечто похожее на разработку начал линейного
программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту
информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже
не а экономистам, а к организаторам производства, с минимумом математики,
без четко описанных алгоритмов, без доказательств теорем – словом, стоит ли
принимать такую книжку во внимание… Но Купманс настаивает на переводе и
издании на западе книги Канторовича. Его имя и идеи становятся известны
всем. Воздадим должное благородству американского ученого!
А самому Леониду Витальевичу – как естественно было бы ему, испытав
первые грозные удары ретроградов, остеречься от «грехов» молодости, забыть
про всю эту экономику и вернуться к математике. Но Л.В.Канторович
продолжает писать математические работы, навеянные экономическими идеями,
участвует и в конкретных разработках на производстве. При этом
(одновременно с Данцигом, но не зная его работ) он разрабатывает метод,
позже названный симплекс-методом. Как только в 50-е годы образуется
маленький просвет и кое что из запретного становится возможным, он
организует группу студентов на экономическом факультете ЛГУ для обучения
методам оптимального планирования. А начиная с 1960 года Леонид Витальевич
занимается только экономической и связанной с нею математической
проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965
году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как
уже говорилось, Нобелевской премией в 1975 году.
II.ОСНОВНЫЕ НАПРАВЛЕНИЯ ИСПОЛЬЗОВАНИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ВОЕННОМ
ДЕЛЕ.
Наиболее распространенными направлениями использования линейного
программирования в военном деле являются:
- задача о перевозках (транспортная задача)
- задача на распределение сил и средств (распределение сил и
средств поражения по целям, распределение сил и средств разведки
и др.)
1. ЗАДАЧИ О ПЕРЕВОЗКАХ (ТРАНСПОРТНАЯ ЗАДАЧА).
Эти задачи являются исторически одними из первых, для решения
которых использовалось линейное программирование. В зависимости от
выбранного критерия эффективности различают транспортные задачи по пробегу,
по стоимости, по времени, совместно по критериям пробега и стоимости, с
ограничениями по пропускной способности дорог и транспорта, задачи в
сетевой постановке и др.
Сформулируем в общем виде транспортную задачу линейного
программирования по критерию стоимости. Эта задача имеет значение тогда,
когда время не является определяющим фактором при организации перевозок.
Пусть имеется m складов, в которых сосредоточен некоторый
однородный продукт (ГСМ, боеприпасы и т.д.) в количествах соответственно
аi(i=1,2,…,m) единиц. Имеется n потребителей этого продукта в количествах
соответственно bj(j=1,2,…,n) единиц. На основании опытов и расчетов
известно, что на доставку одной единицы продук
| |  скачать работу |
Другие рефераты
| 
