Реферат: Применение методов линейного программирования в военном деле. Симплекс-метод - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 82 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

33 РЕФЕРАТ Тема : «Применение методов линейного программирования в военном деле . Симплекс-метод» курсанта 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 потребителей этого продукта в количествах соответственно b j ( j =1,2,…, n ) единиц . На основании опытов и расчетов известно , что на доставку одной единицы продукта с i -то го склада j -тому потребителю затрачивается с ij денежных единиц. Все значения c ij являются постоянными ве личинами . Перечисленные исходные данные помещены в таблице 1. Обозначим через x ij 0 ( i =1,2,…, m ; j =1,2,… n ) количество продукта , планируемого для доставки с i -то го склада j -тому потребителю . Естественно , что если x ij =0 , то доста вка продукта с i - того склада j -тому потребителю не планируется . План обеспечения всех потребителей определяется таблицей (матрицей ): (1) Таблица 1. Склады Потребители Запасы на складах 1 2 … N 1 c n c 12 … c 1n a 1 2 c 21 c 22 … c 2n a 2 … … … … … … M c m1 c m2 … c mn a m Потребность b 1 b 2 … b n Очевидно , можно предложить большое число планов (1) обеспечения потребителей , но при выборе любого из них должны быть учтены условия : (2) (3) Выражения (2) определя ют , что с любого склада можно взять продукта не более имеющихся там запасов . Выражения (3) означают , что каждый потребитель обеспечивается полностью его заявке . По смыслу задачи должно выполняться условие : Последнее выражение означает , что запасов на складах достаточно для снабжения всех потребителей. Суммарная стоимость перевозок для любого выбранного плана (1) определяется выражением : (4) Транспортная задача линейного программирования по критерию стоимости формулируется следующим образом. Найти такие значения x ij (т.е . найти такой план перевозок (1)), удовлетворяющий условиям (2), (3), при которых суммарная стоимость перевозок (4) будет минимальной. При больших m и n эта задача решается на ЭВМ . Для этого нужно ввести в машину исходные данные , помещенные в таблице 1 и воспользоваться разработанной программой . При небольших m и n задача может быть решена вручную с использованием общих методов решения . Для значений m и n до 5-6 задачу часто удается решить путем прикидочных расчетов , перебором вариантов и логических размышлений. Задача . Для обеспечени я ГСМ четырех танковых соединений имеется три склада . Известны запасы ГСМ и потребности в нем соединений . Определение стоимости доставки одной тонны ГСМ из каждого склада в любое соединение . Все исходные данные записаны в таблице 2. Сформулировать задачу л инейного программирования для данных условий и определить такой план снабжения ГСМ соединений , при котором суммарный расход на его провозку будет минимальным. Решение : Обозначим через x ij ( 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 x 11 =350 3 * x 12 =0 4 x 13 =50 x 14 =500 3 * 900 2 x 21 =0 5 x 22 =200 4 x 23 =0 7 x 24 =0 8 300 3 x 31 =0 4 x 32 =250 3 * x 33 =350 5 * x 34 =0 4 60 Потребность в ГСМ 350 450 400 500 Выбор планов зависит от запасов ГСМ на складах и потребностей в нем соединений , что математически определяется выражениями : (2 1 ) (3 1 ) Суммарные расходы на перевозку ГСМ определяются линейными выражениями : (4 1 ) Требует ся определить такие значения x ij (выбрать такой план ) удовлетворяющий выражениям (2 1 ) и (3 1 ), которые критерий эффективности обращают в минимум . Так формулируется задача линейного программирования для данных условий. Эта задача решается элементарными подсч етами и рассуждениями. Отметим в столбцах звездочками минимальные значения стоимости перевозки одной тонны ГСМ . В каждое соединение нужно планировать доставку из того склада , для которого эта стоимость будет наименьшей или близкой к ней , но с учетом расход ов на доставку ГСМ и в другие соединения . Очевидно , в 1-е и 4-е соединение целесообразно завозить ГСМ полностью из 1-го склада , поэтому целесообразно выбрать x 11 =350, x 14 =500 . Во второе соединение выгодно доставить горючее целиком с 3-го склада . Но тогда б удут большие расходы при доставке ГСМ в 3-е соединение из 2-го склада . Поэтому целесообразно выбрать x 13 =50, x 33 =350 , т.е . завести горючее в 3-е соединение с 1-го и 3-го складов , а 200 т . для 2-го соединения завести из склада , x 22 =200, x 32 =250 . Результаты расчетов занесены в таблице 2, по которой удобно проверить выполнение условий (2 1 ), (3 1 ), найдя суммы x ij по строкам и столбцам. При таком плане расходы будут минимальными : Для сравнения , какую можно иметь экономию в средствах , выбрав оптимальный план , рассмотрим один из возможных планов : x 11 =350, x 12 =450, x 13 = x 14 =0, x 21 = x 22 = x 23 =0, x 24 =300, x 31 = x 32 =0, x 33 =400, x 34 =200 При этом плане стоимость перевозок будет равна : Она больше на 1950 единиц K min , что составляет более чем 30%. Полученное оптимальное решение является основой для применения объективного решения на снабжение ГСМ соединений с учетом конкретной обстановки. 2.ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СРЕДСТВ ПОРАЖЕНИЯ. Задачи оптимального распределения средств поражения в общем виде формулируются так : имеется некоторое количество средств поражения и целей . Т ребуется так распределить средства поражения по целям , чтобы общий эффект применения был в определенном смысле оптимален. Поражение противника является одним из важных элементов боевых действий . Поэтому решение задач на поражение является важным этапом пр и планировании и управлении боевыми действиями. Различают два основных типа задач целераспределения : - для средств поражения , находящихся в обороне ; - для средств поражения нападения ; Распределение средств поражения обороны осуществляется в ходе боевых д ействий , выявляемые цели и возникающие условия заранее неизвестны и во многом определяются противником . Расчеты нужно производить очень быстро , что возможно при наличии современных вычислительных средств. Распределение средств нападения по выявленным целям может быть спланировано заранее на основе расчетов . Однако резкой границы между этими вариантами нет потому , что в обоих случаях выявляются новые цели , изменяются условия и потребуется производить перерасчеты. Задача распределения средств поражения при ве дении боевых действий в полной мере очень сложна и требует учета большого числа факторов . Некоторые же частные задачи успешно решаются с помощью линейного программирования. Рассмотрим первую из таких задач . Имеется m различных средств поражения и n целей . Принимаются следующие допущения : - число средств поражения не превосходит числа целей m n ; - цели имеют разную важность , определяемую коэффициентом важности k j ( j =1,2,…, n ); - за каждой целью не может быть закреплено более о дного средства поражения , то есть должно быть обстреляно максимальное число целей ; - известны вероятности p ij поражения i - ым средством j -ой цели , которые составляют таблицу вероятностей поражения : (5) Таблица вероятности поражения вычисляется по соответствующим формулам теории стрельбы. Закреплени е или не закрепление i -то го средства поражения за j -той целью выражается величиной x ij , принимающей значение 1, когда имеется закрепление , и 0, когда его нет. План распределения средств по целям будет определяться таблицей (таблицей 1). За критерий эффекти вности в общем случае выберем взвешенное математическое описание числа уничтоженных целей , которое определяется выражением (6) где k j ( j =1,2,…, m ) – коэффициенты , определяющие важность целей . Если цели имеют одинаковую важность , то k 1 = k 2 =… = k m =1. При этих значениях выражение (6) является математическим ожиданием числа уничтоженных целей . Требование , чтобы каждое средство было закреплено за какой ли бо целью , определяется выражениями ( i =1,2,…, m ) (7) Условия , что за каждой целью закрепляется не более одного средства поражения , определяются вы ражением ( j =1,2,…, n ) (8) В случае знака равенства во всех выражениях (8) имеет место m = n , в противном случае m < n . Первая задача целераспределени я может быть сформулирована следующим образом. Найти такие целые значения x ij 0 ( найти такой план ), удовлетворяющие условиям (7) и (8), которые обращают критерий эффективности (6) в максимум. Как видно , эта задача линейного пр ограммирования , причем транспортного типа . В отличие от задачи на перевозку здесь ищутся значения x ij , принимающие только два возможных значения : 0 и 1. При малых m и n задачи целераспределения могут решаться путем элементарных расчетов и рассуждений. Зада ча . Разведкой обнаружены три равноценные цели противника . Для их уничтожения выделяется командованием три средства поражения . Известны вероятности поражения каждой цели любым средством (таблица 3). Таблица 3. Средства поражения цели Количе ство средств поражения 1 2 3 1 x 11 =1 0,8 * x 12 =0 0,4 x 13 =0 0,8 * 1 2 x 21 =0 0,5 x 22 =0 0,1 x 23 =1 0,7 1 3 x 31 =0 0,2 x 32 =1 0,5 * x 33 =0 0,5 1 Количество целей 1 1 1 Требуется сформулировать задачу линейного программирования по критерию математического ожидания для данных условий и определить оптимальный план целераспределения. Решение . Критерий эффективности в этой задаче согласно формуле (6) определяем выражением : (9) Здесь положено k 1 = k 2 = k 3 =1 , т.к . все цели равноценны . Выражения (7) и (8) для условия задачи будут иметь в ид : (10) (11) Найти такие целые положительные корни x ij уравнений (10) и (11), при которых критерий эффективности (9) примет максимальное значение. Для определения оптимального плана найдем в столбцах таблицы 3 максимальные значения вероятностей и отметим их звездочками . Очевидно , что за второй целью нужно закрепить 3-е средство ( x 3 2 =1). Первое средство одинаково целесообразно закрепить за 1-ой или 3-ей целью . Но так как ближайшее значение к максимальной вероятности для 3-ей цели больше , чем для 1-ой , то целесообразно 1-ое средство закрепить за 1-ой целью ( x 11 =1) , a 2- oe средство за 3-ей целью ( x 23 =1). Максимальное значение математического ожидания числа пораженных целей будет равно : При оптимальном плане будет поражено в среднем две ц ели . Для сравнения рассмотрим следующий план : x 13 =1, x 22 =1 и x 31 =1 . При этом плане средние потери будут равны Таким образом , только за счет оптимального цел ераспределения эффективность средств поражения может быть значительно повышена (в данном примере почти в два раза ). Этот факт имеет не только экономическое значение , но и повышает оперативность выполнения задачи на поражение цели. III . СИМПЛЕКС-МЕТОД. Симплекс-метод решения задачи линейного программирования . Пусть дана система n линейных уравнений с m переменными ( n < m ). (3.22) Пред положим , что среди детерминантов n - го порядка , которые можно составить из коэффициентов n первых столбцов , отличен от нуля. Тогда систему (3.22) можно разре шить относительно переменных x 1 , x 2 , …, x n которые , как и раньше , будем называть базисными переменными . В результате решения системы (3.22) базисные переменные будут выражены через остальные переменные x n +1 , x n +2 , … , x m , называемые свободными . Число свободн ых переменных k = m - n . Мы имеем решение системы (3.22) в виде : (3.23) Свободные переменные остаются произвольными . Давая им различные значения , получим вс е решения системы (3.22). Одно из решений найдем , если все свободные переменные приравняем к нулю . Тогда получим : x 1 = 1 , x 2 = 2 , … , x n = n ; x n +1 = x n +2 =… = x m =0 Если все чис ла 1 , 1 , …, n неотрицательны , то мы будем иметь неотрицательное решение системы (3.22), соответствующее угловой точке (вершине ) многогранника неотрицательных решений , это так называемое опорное решение. Решить систему относительно базисных переменных x 1 , x 2 , …, x n , используя свойства определителей n -го порядка, очень удобно . Мы будем решать эту систему путем последовательного исключения неизвестных . Запишем в виде табли цы коэффициенты уравнений (3.24) и элемент a 11 заключим в рамку (3.27) коэффициенты от неизвестных свободных членов отделим чертой , а элемент a 11 , заключенный в рамочку , будем называть разрешающим элементом . Выпишем соответствующую таблицу для коэффициенто в уравнений (3.26) (3.28) Коэффициент a ’ 21 равен нулю Из уравнения (3.25) следует , что (3.29) На таблице (3.27) соединим элемент a 2 j c разрешающим элементом прямой линией . Рассмотрим прямоугольник , диагональю которого является проведенная линия . Эту диагональ будем называть первой диаг ональю . Второй диагональю является прямая , соединяющая элементы a 21 и a 1 j , обведенные кружком . Как следует из формулы (3.29), чтобы получить элемент a 2 j , нужно из произведения элементов первой диагонали вычесть произведение второй диагонали . Остальные элем енты второй строки вычисляются по этому же правилу . Это правило напоминает правило вычисления детерминантов второго порядка , поэтому будем коротко называть его D - правилом. Переход от таблицы коэффициентов (3.27) к таблице (3.28), совершаемый с помощью D -пр авила , будем называть симплекс преобразованием или S -преобразованием одной таблицы в другую . Очевидно , для выполнения S -преобразования с помощью первого уравнения необходимо , чтобы коэффициент a 11 0 в противном случае перемен ная x 1 в первом уравнении будет отсутствовать. Если теперь возьмем первое уравнение системы (3.22) и третье и проделаем такие же вычисления , то исключим x 1 из третьего уравнения . Продолжая такие же вычисления , исключим x 1 из всех уравнений , кроме первого . Вычисления будем производить в следующем порядке . Сначала запишем таблицу коэффициентов системы (3.22) (3.30) Если a 11 0 , и мы хотим исключить x 1 с помощью первого уравнения , то принимаем элемент a 11 за разрешающий и в таблице (3.30) обводим его рамкой . Строка и столбец , в которых находится разрешающий элемент , называются соответственно разрешающей строкой и разрешающим столбцом . В таблице (3.30) это первая строка и первый столбец. Применяя симплекс преобразование , перейдем к новой таблице . В новой таблице элементы разрешающей строки переписываются без изменений . Все элементы разрешающего столбца , кроме самого разрешающег о элемента заменяются нулями. Остальные элементы новой таблицы вычисляются по D -правилу . Например , для вычисления элемента a ’ ij соединяем элемент a ij на таблице (3.30) с элементом a 11 прямой . В результате имеем первую диагональ . Вторая диагональ получается от соединения элементов a i 1 и a 1 j , обведенных на таблице кружками . По D -правилу имеем При выполнении симплекс преобразования диагонали , изображенные на т аблице (3.30), на самом деле проводить не нужно : они легко выделяются в уме. Выполнив S -преобразование над таблицей (3.30), мы получим новую таблицу (3.31) Этой таблице соответствует система уравнений : (3.32) Система (3.32) эквивалентна первоначальной системе (3.22), но в системе (3.32) пере менная x 1 исключена из всех уравнений , кроме первого . Если в таблице (3.31) элемент a ’ 22 0 , то , приняв его за разрешающий элемент и проделав над таблицей (3.31) S -преобразование , получим новую таблицу . И в системе уравнений , с оответствующей этой таблице , переменная x 2 будет исключена из всех уравнений , кроме второго. Если в таблице (3.31) a ’ 22 =0 , то во втором столбце найдем элемент , не равный нулю , и примем его за разрешающий . Пусть это будет a ’ 12 . Тогда выполняя симплекс преоб разование над таблицей (3.31), мы исключим x 2 из всех уравнений , кроме i - того . Продолжая так дальше , мы после n преобразований придем к таблице , имеющей , например , следующий вид. (3.33) Таблице (3.33) соответствует система уравнений , эквивалентная первоначальной системе . Эта система уравнений имеет вид : (3.34) Можно считать , что система (3.34) решена относительно базисных переменных x 1 , x 2 , … , x n . Переносить члены , соответствующие свободным переменным , в правую часть для фактического решения системы (3.34) относительно базисных переменных не будем , так как в дальнейшем нас будет интересовать решение , где все свободные переменные равны 0. Полагая x n +1 = x n +2 =… = x m =0, получим : Если окажется , что x 1 0, x 2 0, … , x m 0, то совокупность чисел ( x 1 , x 2 , … , x n , 0, 0, … , 0 ) дает неотрицат ельное решение системы. Рассмотрим пример . Дана система уравнений Нужно данную систему разрешить относительно переменных x 1 , x 2 , x 3 . Следовательно свободным и переменными будут x 4 , x 5 , x 6 . Напишем таблицу , соответствующую данной системе уравнений. Решим систему относительно x 1 с помощью первого уравнения . За разрешающий элемент принимаем первый элемент первой строки , и подвергнем таблицу S -преобразованию . Получим новую таблицу , где первая строка переписывается , в первом столбце записываются нули , а остальные элементы вычисляются по D -правилу. Этой таблице соответствует система уравнений , разрешенная относительно x 1 ( x 1 входит только в первое уравнение ). Исключить x 2 удобнее с помощью третьего уравнения , так ка к коэффициент при x 2 в третьем уравнении равен единице . Принимаем его за разрешающий элемент . Пишем новую таблицу Система уравнений , соответствующая этой таблице , разрешена относительно x 1 и x 2 ( x 1 входит только в первое уравнение , а x 2 только в третье ). Для разрешения системы относительно x 3 за разрешающий элемент берем коэффициент при x 3 во втором уравнении . Новая таблица имеет вид Последняя таблица соответствует системе , решенной относительно базисных переменных x 1 , x 2 , x 3 . Полагая свободные переменные x 4 , x 5 , x 6 равными нулю , получим уравнения : -3 x 1 =-18, откуда x 1 =6 -3 x 2 =-6, откуда x 2 =2 -3 x 3 =3 , откуда x 3 =-1 Совокупность чисел x 1 =6, x 2 =2, x 3 =-1, x 4 =0, x 5 =0, x 6 =0 есть одно из решений данной системы . Оно не принадлежит к области допустимых решений , так как одна из координат x 3 отрицательна. Для ре шения задачи линейного программирования важно уметь находить неотрицательные (опорные ) решения данной системы уравнений. Правило выбора разрешающего элемента при отыскании неотрицательного решения системы уравнений. Пусть дана система уравнений (3.36) В системе (3.36) свободные члены можно считать неотрицательными , так как в обеих частях уравнения всегда можно поменять знаки. Если при выполнении симплекс пр еобразований при переходе от одной системы к другой будем следить за тем , чтобы разрешающие элементы были положительными , то на последнем этапе разрешения системы относительно базисных переменных получим систему вида (3.34) и по формулам (3.35) найдем нео т рицательные значения базисных переменных . Составляем отношения свободных членов k к положительным элементам a kj разрешающего столбца и среди чисел выбираем наименьшее значение . Если наименьшее значение достигается при k = i , то i -номер разрешающей строк и , а разрешающим элементом будет a ij . Рассмотрим пример отыскания неотрицательных решений системы уравнений. Пример . Найти неотрицательное решение системы уравнений Пишем таблицу , соответствующую данной системе Пробуем разрешить эту систему относительно x 1 , т.е . переменную x 1 будем считать базисной переменно й . Первый столбец будет базисным столбцом . Составляем отношения свободных членов к положительным элементам первого столбца 10/2=5; 4/7. Наименьшее из этих чисел 4/7. Числа 4 и 7 находятся во второй строке . Следовательно разрешающей строкой будет вторая ст р ока и разрешающим элементом число 7. Выполняя симплекс преобразование , получим новую таблицу Этой таблице соответствует система уравнений , разрешенная от носительно базисной переменной x 1 . Так как обе части любого уравнения системы можно умножать и делить на любое постоянное число (система при этом будет эквивалентна прежней ), то если строки таблицы имеют общий множитель , на него можно сократить . Последняя строка предыдущей таблицы имеет общий множитель 7; сокращая на него , получим таблицу Введем в базис переменную x 3 , т.е . примем за разрешающий столбец тре тий столбец. Из двух отношений 62/13 и 10/3 меньшим является второе . Следовательно , разрешающим элементом будет 3. Выполняя симплекс преобразование получим таблицу Первую строку сокращаем на 28, вторую на 21 Введем в базис переменную x 2 . Разрешающим элементом бу дет 5. Снова выполняя симплекс преобразования , получим таблицу Последнюю строку сокращаем на 3 Эта таблица соответствует системе уравнений , разрешенной относительно базисных переменных x 1 , x 2 , x 3 . Свободными переменными здесь являются x 4 и x 5 . Полагая свободные переменные равными нулю , получим : 5 x 1 =12 , x 1 = 12/5; 5 x 2 =2, x 2 =2/5; 5 x 3 =18, x 3 =18/5; Совокупность чисел x 1 =12/5; x 2 =2/5; x 3 =18/5; x 4 =0; x 5 =0 Дает неотрицательный ответ данной системы уравнений . Эти числа можно рассматривать как координаты угловой точки (вершины ) множества (многогранника ) допустимых реш ений. ЛИТЕРАТУРА Малявко К.Ф . «Применение математических методов в военном деле». Журко М.Д . «Математические методы и основы их применения в управлении войсками». Журнал Квант № 6 за 1989г. Квант № 7 за 19 79г.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Что есть у человека - одежда, свет, интернет. А что есть у мудрых кошек - мех, "прибор ночного видения" и мы...
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Применение методов линейного программирования в военном деле. Симплекс-метод", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru