РЕФЕРАТ
Тема: «Застосування методів лінійного програмування у військовій справі. Симплекс-метод »
курсанти 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.
| Склади | Споживачі | Запаси на |
| | | Складах |
| | 1 | 2 | ... | N | |
| 1 | | | ... | | a1 |
| | Cn | c12 | | c1n | |
| 2 | | | ... | | a2 |
| | C21 | c22 | | c2n | |
| ... | ... | ... | ... | ... | ... |
| M | | | ... | | am |
| | Cm1 | cm2 | | cmn | |
| Потребнос | b1 | b2 | ... | bn | |
| ть | | | | | |
Очевидно, можна запропонувати велику кількість планів (1) забезпеченняспоживачів, але при виборі будь-якого з них повинні бути враховані умови:
(2)
(3)
Вирази (2) визначають, що з будь-якого складу можна взяти продуктуне більше наявних там запасів. Вирази (3) означають, що коженспоживач забезпечується повністю його заявці. За змістом завдання повинновиконуватися умова:
Останній вираз означає, що запасів на складах достатньо дляпостачання всіх споживачів.
Сумарна вартість перевезень для будь-якого вибраного плану (1)визначається виразом:
(4)
Транспортна задача лінійного програмування за критеріємвартості формулюється наступним чином.
Знайти такі значення xij (тобто знайти такий план перевезень (1)),задовольняє умовам (2), (3), при яких сумарна вартістьперевезень (4) буде мінімальною.
При великих m і n це завдання вирішується на ЕОМ. Для цього потрібноввести в машину вихідні дані, вміщені в таблиці 1 і скористатисярозробленою програмою. При невеликих m і n задача може бути вирішенавручну з використанням загальних методів рішення. Для значень m і n до 5-6завдання часто вдається вирішити шляхом приблизних розрахунків, перебором варіантіві логічних міркувань.
Завдання. Для забезпечення ПММ чотирьох танкових з'єднань є трискладу. Відомі запаси ПММ і потреби в ньому сполук. Визначеннявартості доставки однієї тонни ПММ з кожного складу в будь-яке з'єднання.
Всі вихідні дані записані в таблиці 2.
Сформулювати задачу лінійного програмування для даних умові визначити такий план постачання ПММ сполук, при якому сумарнийвитрати на його провезення буде мінімальним.
Рішення: Позначимо через xij (i = 1,2,3; j = 1,2,3,4) кількість ПММ,планованих для доставки з i-того складу (i = 1,2,3) j-тому з'єднанню
(j = 1,2,3,4).
Таблиця 2.
| Склади | З'єднання | Запаси ПММ |
| | | На складах |
| | 1 | 2 | 3 | 4 | |
| 1 | x11 = 350 | x12 = 0 | x13 = 50 | x14 = 500 | 900 |
| | 3 * | 4 | | 3 * | |
| 2 | x21 = 0 | x22 = 200 | x23 = 0 | x24 = 0 | 300 |
| | 5 | 4 | 7 | 8 | |
| 3 | x31 = 0 | x32 = 250 | x33 = 350 | x34 = 0 | 60 |
| | 4 | 3 * | 5 * | 4 | |
| Потребнос | 350 | 450 | 400 | 500 | |
| ть в ПММ | | | | | |
Вибір планів залежить від запасів ПММ на складах і потреб в ньомуз'єднань, що математично визначається виразами:
(21)
(31)
Сумарні витрати на перевезення ПММ визначаються лінійнимивиразами:
(41)
Потрібно визначити такі значення xij (вибрати такий план)задовольняє виразами (21) і (31), які критерій ефективностізвертають в мінімум. Так формулюється задача лінійного програмування дляданих умов.
Це завдання вирішується елементарними підрахунками й міркуваннями.
Відзначимо у стовпцях зірочками мінімальні значення вартостіперевезення однієї тонни ПММ. У кожне підключення потрібно планувати доставкуз того складу, для якого ця вартість буде найменшою або близькою донеї, але з урахуванням витрат на доставку ПММ і в інші з'єднання. Очевидно,в 1-е і 4-е підключення доцільно завозити ПММ повністю з 1-го складу,тому доцільно вибрати x11 = 350, x14 = 500. По друге з'єднаннявигідно доставити пальне цілком з 3-го складу. Але тоді будуть великівитрати при доставці ПММ у 3-є з'єднання з 2-го складу. Томудоцільно вибрати x13 = 50, x33 = 350, тобто завести пальне в 3-ез'єднання з 1-го і 3-го складів, а 200 т. для 2-го з'єднання завести зскладу, x22 = 200, x32 = 250. Результати розрахунків занесені в таблиці 2, заякої зручно перевірити виконання умов (21), (31), знайшовши суми xij порядках і стовпцях.
При такому плані витрати будуть мінімальними:
Для порівняння, яку можна мати економію в коштах, вибравшиоптимальний план, розглянемо один з можливих планів: x11 = 350, x12 = 450, x13 = x14 = 0, x21 = x22 = x23 = 0, x24 = 300, x31 = x32 = 0, x33 = 400, x34 = 200
При цьому плані вартість перевезень буде дорівнює:
Вона більше на 1950 одиниць Kmin, що складає більш ніж 30%.
Отримане оптимальне рішення є основою для застосуванняоб'єктивного рішення на постачання ПММ з'єднань з урахуванням конкретноїобстановки.
2.ЗАДАЧІ ОПТИМАЛЬНОГО РОЗПОДІЛУ ЗАСОБІВ УРАЖЕННЯ.
Завдання оптимального розподілу засобів ураження в загальному виглядіформулюються так: є деяка кількість засобів ураження і цілей.
Потрібно так розподілити засоби ураження по цілях, щоб загальний ефектзастосування був у певному сенсі оптимальний.
Поразка противника є одним з важливих елементів бойовихдій. Тому рішення завдань на поразку є важливим етапом припланування і управління бойовими діями.
Розрізняють два основних типи завдань целераспределенія:
- для засобів ураження, що знаходяться в обороні;
- для засобів ураження нападу;
Розподіл засобів ураження оборони здійснюється в ходібойових дій, які виявляються цілі і виникають умови заздалегідь невідомі ібагато в чому визначаються супротивником. Розрахунки потрібно робити дуже швидко,що можливо за наявності сучасних обчислювальних засобів.
Розподіл засобів нападу по виявлених цілях може бутисплановано заздалегідь на основі розрахунків. Однак різкої межі між цимиваріантами немає тому, що в обох випадках виявляються нові цілі,змінюються умови і буде потрібно проводити перерахунки.
Завдання розподілу засобів ураження при веденні бойових дійповною мірою дуже складна і вимагає врахування великої кількості факторів.
Деякі ж приватні завдання успішно вирішуються за допомогою лінійногопрограмування.
Розглянемо перший з таких задач. Є m різних засобівпоразки і n цілей. Приймаються наступні допущення:
- число засобів ураження не перевершує числа цілей m (n;
- цілі мають різну важливість, яка визначається коефіцієнтом важливості kj (j = 1,2, ..., n );
- за кожною метою не може бути закріплено більше одного засоби ураження, тобто має бути обстріляно Максимальна кількість цілей;
- відомі ймовірності pij поразки i-им засобом j-ой цілі, які складають таблицю ймовірностей поразки:
(5)
Таблиця вірогідності поразки обчислюється за відповіднимиформулами теорії стрільби.
Закріплення або не закріплення i-того засоби ураження за j-тоїметою виражається величиною xij, що приймає значення 1, коли єзакріплення, і 0, коли його немає.
План розподілу коштів за цілями буде визначатися таблицею
(таблиці 1). За критерій ефективності в загальному випадку виберемо зваженематематичний опис числа знищених цілей, яке визначаєтьсявиразом
(6)
де kj (j = 1,2, ..., m) - коефіцієнти, що визначають важливість цілей.
Якщо цілі мають однакову важливість, то k1 = k2 = ... = km = 1. При цих значенняхвираз (6) є математичним очікуванням числа знищених цілей.
Вимога, щоб кожен засіб було закріплено за будь якою метою,визначається виразами
(i = 1,2, ..., m) (7)
Умови, що за кожною метою закріплюється не більше одного засобуураження, визначаються виразом
(j = 1,2, ..., n) (8)
У разі знаку рівності у всіх виразах (8) має місце m = n, вІнакше m
