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

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

РЕФЕРАТ


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

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


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

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

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

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


ПЛАН


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

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

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

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

поражения

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

  2. Заключение

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


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

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

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

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

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

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

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

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

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

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

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

А самому Леониду Витальевичу – как естественно было бы ему, испытав 1-ые суровые удары ретроградов, остеречься от Применение методов линейного программирования в военном деле. Симплекс-метод - реферат «грехов» юности, запамятовать про всю эту экономику и возвратиться к арифметике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими мыслями, участвует и в определенных разработках на производстве. При всем этом (сразу с Данцигом, но не зная его работ) он разрабатывает способ, позднее нареченный симплекс-методом. Как в 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


cn


c12



c1n

a1

2

c21


c22


c2n

a2

M

cm1


cm2


cmn

am

Потребность

b1

b2

bn



Разумеется, можно предложить огромное число планов (1) обеспечения потребителей, но при выборе хоть какого из их должны быть учтены условия:


(2)


(3)


Выражения (2) определяют, что с хоть какого склада Применение методов линейного программирования в военном деле. Симплекс-метод - реферат можно взять продукта менее имеющихся там припасов. Выражения (3) означают, что каждый потребитель обеспечивается стопроцентно его заявке. По смыслу задачки должно производиться условие:



Последнее выражение значит, что припасов на складах довольно для снабжения всех потребителей.

Суммарная цена перевозок для хоть какого избранного плана (1) определяется выражением:


(4)


Транспортная задачка линейного программирования Применение методов линейного программирования в военном деле. Симплекс-метод - реферат по аспекту цены формулируется последующим образом.

Отыскать такие значения xij (т.е. отыскать таковой план перевозок (1)), удовлетворяющий условиям (2), (3), при которых суммарная цена перевозок (4) будет малой.

При огромных m и n эта задачка решается на ЭВМ. Для этого необходимо ввести в машину начальные данные, помещенные в таблице 1 и пользоваться разработанной Применение методов линейного программирования в военном деле. Симплекс-метод - реферат программкой. При маленьких m и n задачка может быть решена вручную с внедрением общих способов решения. Для значений m и n до 5-6 задачку нередко удается решить методом прикидочных расчетов, перебором вариантов и логических раздумий.

Задачка. Для обеспечения ГСМ 4 танковых соединений имеется три склада. Известны припасы ГСМ и потребности в нем соединений Применение методов линейного программирования в военном деле. Симплекс-метод - реферат. Определение цены доставки одной тонны ГСМ из каждого склада в хоть какое соединение. Все начальные данные записаны в таблице 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

3*

x12=0

4

x13=50


x14=500

3*

900

2

x21=0

5

x22=200

4

x23=0

7

x24=0

8

300
3

x31=0

4

x32=250

3*

x33=350

5*

x34=0

4

60
Потребность в ГСМ 350 450 400 500

Выбор планов находится в зависимости от припасов ГСМ на складах и потребностей в нем соединений Применение методов линейного программирования в военном деле. Симплекс-метод - реферат, что математически определяется выражениями:


(21)

(31)


Суммарные расходы на перевозку ГСМ определяются линейными выражениями:


(41)


Требуется найти такие значения xij (избрать таковой план) удовлетворяющий выражениям (21) и (31), которые аспект эффективности обращают в минимум. Так формулируется задачка линейного программирования для данных критерий.

Эта задачка решается простыми подсчетами и рассуждениями.

Отметим в столбцах звездочками малые значения цены перевозки Применение методов линейного программирования в военном деле. Симплекс-метод - реферат одной тонны ГСМ. В каждое соединение необходимо планировать доставку из того склада, для которого эта цена будет меньшей либо близкой к ней, но с учетом расходов на доставку ГСМ и в другие соединения. Разумеется, в 1-е и 4-е соединение целенаправлено завозить ГСМ стопроцентно из 1-го склада, потому целенаправлено избрать Применение методов линейного программирования в военном деле. Симплекс-метод - реферат x11=350, x14=500. Во 2-ое соединение прибыльно доставить горючее полностью с 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=x Применение методов линейного программирования в военном деле. Симплекс-метод - реферат14=0, x21=x22=x23=0,

x24=300, x31=x32=0, x33=400, x34=200

При всем этом плане цена перевозок будет равна:



Она больше на 1950 единиц Kmin, что составляет более чем 30%.

Приобретенное среднее решение является основой для внедрения беспристрастного решения на снабжение ГСМ соединений с учетом определенной обстановки.


2.Задачки Рационального Рассредотачивания СРЕДСТВ ПОРАЖЕНИЯ Применение методов линейного программирования в военном деле. Симплекс-метод - реферат.


Задачки рационального рассредотачивания средств поражения в общем виде формулируются так: имеется некое количество средств поражения и целей. Требуется так распределить средства поражения по целям, чтоб общий эффект внедрения был в определенном смысле оптимален.

Поражение противника является одним из принципиальных частей боевых действий. Потому решение задач на поражение является принципиальным шагом при Применение методов линейного программирования в военном деле. Симплекс-метод - реферат планировании и управлении боевыми действиями.

Различают два главных типа задач целераспределения:

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

Рассредотачивание средств нападения по выявленным целям может быть спланировано заблаговременно на базе расчетов. Но резкой границы меж этими вариациями нет поэтому, что в обоих случаях выявляются новые цели, меняются условия и будет нужно создавать перерасчеты.

Задачка рассредотачивания средств поражения при ведении Применение методов линейного программирования в военном деле. Симплекс-метод - реферат боевых действий полностью очень сложна и просит учета огромного числа причин. Некие же личные задачки удачно решаются при помощи линейного программирования.

Разглядим первую из таких задач. Имеется m разных средств поражения и n целей. Принимаются последующие допущения:


(5)


Таблица вероятности поражения рассчитывается по подходящим формулам теории стрельбы Применение методов линейного программирования в военном деле. Симплекс-метод - реферат.

Закрепление либо не закрепление i-того средства поражения за j-той целью выражается величиной xij, принимающей значение 1, когда имеется закрепление, и 0, когда его нет.

План рассредотачивания средств по целям будет определяться таблицей (таблицей 1). За аспект эффективности в общем случае выберем взвешенное математическое описание числа уничтоженных целей, которое определяется выражением


(6)


где Применение методов линейного программирования в военном деле. Симплекс-метод - реферат kj (j=1,2,…,m) – коэффициенты, определяющие значимость целей. Если цели имеют схожую значимость, то k1=k2=…=km=1. При этих значениях выражение (6) является математическим ожиданием числа уничтоженных целей. Требование, чтоб каждое средство было закреплено за какой или целью, определяется выражениями


(i=1,2,…,m) (7)


Условия, что за каждой целью закрепляется менее 1-го средства Применение методов линейного программирования в военном деле. Симплекс-метод - реферат поражения, определяются выражением


(j=1,2,…,n) (8)


В случае знака равенства во всех выражениях (8) имеет место m=n, в неприятном случае m

Отыскать такие целые значения xij0 (отыскать таковой план), удовлетворяющие условиям (7) и (8), которые обращают аспект эффективности (6) в максимум.

Как видно, эта задачка линейного программирования Применение методов линейного программирования в военном деле. Симплекс-метод - реферат, при этом транспортного типа. В отличие от задачки на перевозку тут ищутся значения xij, принимающие только два вероятных значения: 0 и 1.

При малых m и n задачки целераспределения могут решаться методом простых расчетов и рассуждений.

Задачка. Разведкой обнаружены три равноценные цели противника. Для их ликвидирования выделяется командованием три средства Применение методов линейного программирования в военном деле. Симплекс-метод - реферат поражения. Известны вероятности поражения каждой цели хоть каким средством (таблица 3).


Таблица 3.

Средства поражения

цели

Количество

средств

поражения

1 2 3

1

x11=1

0,8*

x12=0

0,4

x13=0

0,8*

1

2

x21=0

0,5

x22=0

0,1

x23=1

0,7

1
3

x31=0

0,2

x32=1

0,5*

x33=0

0,5

1
Количество целей 1 1 1

Требуется сконструировать задачку линейного программирования по аспекту математического ожидания для данных критерий и найти лучший план целераспределения.

Решение. Аспект эффективности в этой задачке согласно формуле Применение методов линейного программирования в военном деле. Симплекс-метод - реферат (6) определяем выражением:


(9)


Тут положено k1=k2=k3=1, т.к. все цели равноценны. Выражения (7) и (8) для условия задачки будут иметь вид:


(10)


(11)


Отыскать такие целые положительные корешки xij уравнений (10) и (11), при которых аспект эффективности (9) воспримет наибольшее значение.

Для определения рационального плана найдем в столбцах таблицы 3 наибольшие значения вероятностей и Применение методов линейного программирования в военном деле. Симплекс-метод - реферат отметим их звездочками. Разумеется, что за 2-ой целью необходимо закрепить 3-е средство (x32=1). 1-ое средство идиентично целенаправлено закрепить за 1-ой либо 3-ей целью. Но потому что наиблежайшее значение к наибольшей вероятности для 3-ей цели больше, чем для 1-ой, то целенаправлено 1-ое средство закрепить за 1-ой целью (x11=1), a 2-oe средство за Применение методов линейного программирования в военном деле. Симплекс-метод - реферат 3-ей целью (x23=1).

Наибольшее значение математического ожидания числа пораженных целей будет равно:



При рациональном плане будет поражено в среднем две цели. Для сопоставления разглядим последующий план: x13=1, x22=1 и x31=1. При всем этом плане средние утраты будут равны



Таким макаром, только за счет рационального целераспределения эффективность средств поражения может быть Применение методов линейного программирования в военном деле. Симплекс-метод - реферат существенно повышена (в данном примере практически вдвое). Данный факт имеет не только лишь экономическое значение, да и увеличивает оперативность выполнения задачки на поражение цели.


III.СИМПЛЕКС-МЕТОД.


Симплекс-метод решения задачки линейного программирования. Пусть дана система n линейных уравнений с m переменными (n

(3.22)


Представим, что посреди детерминантов n-го Применение методов линейного программирования в военном деле. Симплекс-метод - реферат порядка, которые можно составить из коэффициентов n первых столбцов, отличен от нуля.



Тогда систему (3.22) можно разрешить относительно переменных x1, x2, …,xn которые, по-прежнему, будем именовать базовыми переменными. В итоге решения системы (3.22) базовые переменные будут выражены через другие переменные xn+1, xn+2, …, xm, именуемые свободными. Число свободных переменных k=m-n Применение методов линейного программирования в военном деле. Симплекс-метод - реферат. Мы имеем решение системы (3.22) в виде:


(3.23)


Свободные переменные остаются случайными. Давая им разные значения, получим все решения системы (3.22). Одно из решений найдем, если все свободные переменные приравняем к нулю. Тогда получим:


x1=1, x2=2, …, xn=n; xn+1=xn+2=…=xm=0


Если все числа 1, 1, …,n неотрицательны, то мы будем иметь Применение методов линейного программирования в военном деле. Симплекс-метод - реферат неотрицательное решение системы (3.22), соответственное угловой точке (верхушке) полиэдра неотрицательных решений, это так называемое опорное решение.

Решить систему относительно базовых переменных x1, x2, …,xn, используя характеристики определителей n-го порядка, очень комфортно. Мы будем решать эту систему методом поочередного исключения неведомых.

Запишем в виде таблицы коэффициенты уравнений (3.24) и элемент a11 заключим Применение методов линейного программирования в военном деле. Симплекс-метод - реферат в рамку


(3.27)


коэффициенты от неведомых свободных членов отделим чертой, а элемент a11, заключенный в рамочку, будем именовать разрешающим элементом.

Выпишем подобающую таблицу для коэффициентов уравнений (3.26)


(3.28)


Коэффициент a’21 равен нулю

Из уравнения (3.25) следует, что


(3.29)


На таблице (3.27) соединим элемент a2j c разрешающим элементом прямой линией. Разглядим прямоугольник, диагональю которого является Применение методов линейного программирования в военном деле. Симплекс-метод - реферат проведенная линия. Эту диагональ будем именовать первой диагональю. 2-ой диагональю является ровная, соединяющая элементы a21 и a1j, обведенные кружком. Как надо из формулы (3.29), чтоб получить элемент a2j, необходимо из произведения частей первой диагонали отнять произведение 2-ой диагонали. Другие элементы 2-ой строчки рассчитываются по этому же правилу. Это правило Применение методов линейного программирования в военном деле. Симплекс-метод - реферат припоминает правило вычисления детерминантов второго порядка, потому будем кратко именовать его D-правилом.

Переход от таблицы коэффициентов (3.27) к таблице (3.28), совершаемый при помощи D-правила, будем именовать симплекс преобразованием либо S-преобразованием одной таблицы в другую.

Разумеется, для выполнения S-преобразования при помощи первого уравнения нужно, чтоб коэффициент a110 в неприятном Применение методов линейного программирования в военном деле. Симплекс-метод - реферат случае переменная x1 в первом уравнении будет отсутствовать.

Если сейчас возьмем 1-ое уравнение системы (3.22) и третье и проделаем такие же вычисления, то исключим x1 из третьего уравнения. Продолжая такие же вычисления, исключим x1 из всех уравнений, не считая первого. Вычисления будем создавать в последующем порядке. Поначалу запишем таблицу коэффициентов системы Применение методов линейного программирования в военном деле. Симплекс-метод - реферат (3.22)


(3.30)


Если a110, и мы желаем исключить x1 при помощи первого уравнения, то принимаем элемент a11 за разрешающий и в таблице (3.30) обводим его рамкой. Строчка и столбец, в каких находится разрешающий элемент, именуются соответственно разрешающей строчкой и разрешающим столбцом. В таблице (3.30) это 1-ая строчка и 1-ый столбец Применение методов линейного программирования в военном деле. Симплекс-метод - реферат.

Применяя симплекс преобразование, перейдем к новейшей таблице. В новейшей таблице элементы разрешающей строчки переписываются без конфигураций. Все элементы разрешающего столбца, не считая самого разрешающего элемента заменяются нулями.

Другие элементы новейшей таблицы рассчитываются по D-правилу. К примеру, для вычисления элемента a’ij соединяем элемент aij на таблице (3.30) с элементом a Применение методов линейного программирования в военном деле. Симплекс-метод - реферат11 прямой. В итоге имеем первую диагональ. 2-ая диагональ выходит от соединения частей ai1 и a1j, обведенных на таблице кружками. По D-правилу имеем



При выполнении симплекс преобразования диагонали, изображенные на таблице (3.30), по сути проводить не надо: они просто выделяются в уме.

Выполнив S-преобразование над таблицей (3.30), мы Применение методов линейного программирования в военном деле. Симплекс-метод - реферат получим новейшую таблицу


(3.31)


Этой таблице соответствует система уравнений:


(3.32)


Система (3.32) эквивалентна начальной системе (3.22), но в системе (3.32) переменная x1 исключена из всех уравнений, не считая первого. Если в таблице (3.31) элемент a’220, то, приняв его за разрешающий элемент и проделав над таблицей (3.31) S-преобразование, получим новейшую таблицу. И в системе уравнений, соответственной этой Применение методов линейного программирования в военном деле. Симплекс-метод - реферат таблице, переменная x2 будет исключена из всех уравнений, не считая второго.

Если в таблице (3.31) a’22=0, то во 2-м столбце найдем элемент, не равный нулю, и примем его за разрешающий. Пусть это будет a’12. Тогда выполняя симплекс преобразование над таблицей (3.31), мы исключим x2 из всех уравнений, не считая i-того Применение методов линейного программирования в военном деле. Симплекс-метод - реферат. Продолжая так далее, мы после n преобразований придем к таблице, имеющей, к примеру, последующий вид.


(3.33)


Таблице (3.33) соответствует система уравнений, эквивалентная начальной системе. Эта система уравнений имеет вид:


(3.34)


Можно считать, что система (3.34) решена относительно базовых переменных x1, x2, …, xn. Переносить члены, надлежащие свободным переменным, в правую часть для фактического Применение методов линейного программирования в военном деле. Симплекс-метод - реферат решения системы (3.34) относительно базовых переменных не будем, потому что в предстоящем нас будет заинтересовывать решение, где все свободные переменные равны 0.

Полагая xn+1=xn+2=…=xm=0, получим:



Если окажется, что x10, x20, …, xm0, то совокупа чисел (x1, x2, …, xn, 0, 0, …, 0) дает неотрицательное решение системы.

Разглядим пример. Дана система уравнений



Необходимо данную систему разрешить относительно Применение методов линейного программирования в военном деле. Симплекс-метод - реферат переменных x1, x2, x3. Как следует свободными переменными будут x4, x5, x6. Напишем таблицу, подобающую данной системе уравнений.



Решим систему относительно x1 при помощи первого уравнения. За разрешающий элемент принимаем 1-ый элемент первой строчки, и подвергнем таблицу S-преобразованию. Получим новейшую таблицу, где 1-ая строчка переписывается, в первом Применение методов линейного программирования в военном деле. Симплекс-метод - реферат столбце записываются нули, а другие элементы рассчитываются по D-правилу.



Этой таблице соответствует система уравнений, разрешенная относительно x1 (x1 заходит исключительно в 1-ое уравнение). Исключить x2 удобнее при помощи третьего уравнения, потому что коэффициент при x2 в 3-ем уравнении равен единице. Принимаем его за разрешающий элемент. Пишем новейшую таблицу



Система уравнений Применение методов линейного программирования в военном деле. Симплекс-метод - реферат, соответственная этой таблице, разрешена относительно x1 и x2 (x1 заходит исключительно в 1-ое уравнение, а x2 исключительно в третье).

Для разрешения системы относительно x3 за разрешающий элемент берем коэффициент при x3 во 2-м уравнении. Новенькая таблица имеет вид



Последняя таблица соответствует системе, решенной относительно базовых переменных x1, x2, x Применение методов линейного программирования в военном деле. Симплекс-метод - реферат3. Полагая свободные переменные x4, x5, x6 равными нулю, получим уравнения:


-3x1=-18, откуда x1=6

-3x2=-6, откуда x2=2

-3x3=3, откуда x3=-1


Совокупа чисел x1=6, x2=2, x3=-1, x4=0, x5=0, x6=0 есть одно из решений данной системы. Оно не принадлежит к области допустимых решений, потому что одна из координат x3 отрицательна.

Для решения задачки Применение методов линейного программирования в военном деле. Симплекс-метод - реферат линейного программирования принципиально уметь отыскивать неотрицательные (опорные) решения данной системы уравнений.


Правило выбора разрешающего элемента при отыскании неотрицательного решения системы уравнений.

Пусть дана система уравнений


(3.36)


В системе (3.36) свободные члены можно считать неотрицательными, потому что в обеих частях уравнения всегда можно поменять знаки.

Если при выполнении симплекс преобразований Применение методов линейного программирования в военном деле. Симплекс-метод - реферат при переходе от одной системы к другой будем смотреть за тем, чтоб разрешающие элементы были положительными, то на завершающем шаге разрешения системы относительно базовых переменных получим систему вида (3.34) и по формулам (3.35) найдем неотрицательные значения базовых переменных. Составляем дела свободных членов k к положительным элементам akj разрешающего столбца и посреди чисел избираем Применение методов линейного программирования в военном деле. Симплекс-метод - реферат меньшее значение. Если меньшее значение достигается при k=i, то i-номер разрешающей строчки, а разрешающим элементом будет aij.

Разглядим пример отыскания неотрицательных решений системы уравнений.

Пример. Отыскать неотрицательное решение системы уравнений



Пишем таблицу, подобающую данной системе



Пробуем разрешить эту систему относительно x1, т.е. переменную x1 будем считать базовой переменной Применение методов линейного программирования в военном деле. Симплекс-метод - реферат. 1-ый столбец будет базовым столбцом. Составляем дела свободных членов к положительным элементам первого столбца 10/2=5; 4/7. Меньшее из этих чисел 4/7. Числа 4 и 7 находятся во 2-ой строке. Как следует разрешающей строчкой будет 2-ая строчка и разрешающим элементом число 7. Выполняя симплекс преобразование, получим новейшую таблицу



Этой таблице соответствует система уравнений, разрешенная относительно базовой переменной x Применение методов линейного программирования в военном деле. Симплекс-метод - реферат1. Потому что обе части хоть какого уравнения системы можно множить и разделять на хоть какое неизменное число (система при всем этом будет эквивалентна прежней), то если строчки таблицы имеют общий множитель, на него можно уменьшить. Последняя строчка предшествующей таблицы имеет общий множитель 7; сокращая на него, получим таблицу



Введем в базис Применение методов линейного программирования в военном деле. Симплекс-метод - реферат переменную x3, т.е. примем за разрешающий столбец 3-ий столбец.

Из 2-ух отношений 62/13 и 10/3 наименьшим является 2-ое. Как следует, разрешающим элементом будет 3. Выполняя симплекс преобразование получим таблицу



Первую строчку сокращаем на 28, вторую на 21


Введем в базис переменную x2. Разрешающим элементом будет 5. Опять выполняя симплекс преобразования, получим таблицу



Последнюю строчку сокращаем на Применение методов линейного программирования в военном деле. Симплекс-метод - реферат 3



Эта таблица соответствует системе уравнений, разрешенной относительно базовых переменных x1, x2, x3. Свободными переменными тут являются x4 и x5. Полагая свободные переменные равными нулю, получим:

5x1=12, x1=12/5; 5x2=2, x2=2/5; 5x3=18, x3=18/5;

Совокупа чисел x1=12/5; x2=2/5; x3=18/5; x4=0; x5=0

Дает неотрицательный ответ данной системы уравнений. Эти числа можно Применение методов линейного программирования в военном деле. Симплекс-метод - реферат рассматривать как координаты угловой точки (верхушки) огромного количества (полиэдра) допустимых решений.


ЛИТЕРАТУРА


Малявко К.Ф. «Применение математических способов в военном

деле».

Журко М.Д. «Математические способы и базы их внедрения

в управлении войсками».

Журнальчик Квант №6 за 1989г.

Квант №7 за 1979г.




primenenie-sistem-dimohodov.html
primenenie-slov-obrazovannih-grafiko-punktuacionnim-sposobom-slovoobrazovaniya-v-sredstvah-massovoj-informacii-kursovaya-rabota.html
primenenie-sociologicheskih-metodik-dlya-izucheniya-zhurnalistov.html