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

РЕФЕРАТ

Тема:
«Применение
методов линейного
программирования
в

военном
деле. Симплекс-метод»

курсанта
2-го курса I
взв. 8-й роты

Дальневосточного
военного института

им. К.К.
Рокоссовского

Верещак
Дмитрия Владимировича

ПЛАН

Что такое
линейное
программирование

Основные
направления
использования
линейного
программирования
в военном деле

1.Задачи
о перевозках
(транспортная)
задача

2.Задачи
оптимального
распределения
средств

поражения

Симплекс-метод

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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