Применение методов линейного программирования в военном деле. Симплекс-метод
Применение методов линейного программирования в военном деле. Симплекс-метод
РЕФЕРАТ
Тема: «Применение
методов линейного программирования в
военном деле.
Симплекс-метод»
курсанта 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) единиц. На
основании опытов и расчетов известно, что на доставку одной единицы продукта с i-того склада j-тому потребителю затрачивается сij
денежных единиц.
Все значения cij являются постоянными величинами. Перечисленные исходные данные
помещены в таблице 1.
Обозначим через xij³0
(i=1,2,…,m; j=1,2,…n) количество продукта,
планируемого для доставки с i-того склада j-тому потребителю. Естественно, что если xij=0, то доставка продукта с i-того склада j-тому потребителю не планируется. План обеспечения всех потребителей
определяется таблицей (матрицей):
(1)
Таблица 1.
|