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

РЕФЕРАТ

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

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

курсанта 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-тому потребителю не планируется. Планобеспечения всех потребителей определяется таблицей (матрицей):

<img src="/cache/referats/2522/image002.gif" v:shapes="_x0000_i1025"> (1)

Таблица 1.

Потребители

Запасы на складах

…

<img src="/cache/referats/2522/image004.gif" v:shapes="_x0000_s1045"><img src="/cache/referats/2522/image005.gif" v:shapes="_x0000_s1046"><img src="/cache/referats/2522/image006.gif" v:shapes="_x0000_s1043"><img src="/cache/referats/2522/image005.gif" v:shapes="_x0000_s1037"><img src="/cache/referats/2522/image004.gif" v:shapes="_x0000_s1036"> 1

c12

…

c1n

c21

c22

…

c2n

<img src="/cache/referats/2522/image005.gif" v:shapes="_x0000_s1047"><img src="/cache/referats/2522/image006.gif" v:shapes="_x0000_s1039"><img src="/cache/referats/2522/image004.gif" v:shapes="_x0000_s1038"> …

…

cm1

cm2

…

cmn

Потребность

…

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

<img src="/cache/referats/2522/image008.gif" v:shapes="_x0000_i1026"> (2)

<img src="/cache/referats/2522/image010.gif" v:shapes="_x0000_i1027"> (3)

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

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

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

<img src="/cache/referats/2522/image014.gif" v:shapes="_x0000_i1029"> (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.

Склады

Соединения

Запасы ГСМ на складах

x11=350

x12=0

x13=50

x14=500

900

x21=0

x22=200

x23=0

x24=0

300

x31=0

x32=250

x33=350

x34=0

Потребность в ГСМ

350

450

400

500

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

<img src="/cache/referats/2522/image016.gif" v:shapes="_x0000_i1030"> (21)

<img src="/cache/referats/2522/image018.gif" v:shapes="_x0000_i1031"> (31)

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

<img src="/cache/referats/2522/image020.gif" v:shapes="_x0000_i1032"> (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-ой цели, которые составляюттаблицу вероятностей поражения <img src="/cache/referats/2522/image026.gif" v:shapes="_x0000_i1035">

<img src="/cache/referats/2522/image028.gif" v:shapes="_x0000_i1036"> (5)

Таблица вероятности поражения вычисляется по соответствующимформулам теории стрельбы.

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

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

<img src="/cache/referats/2522/image030.gif" v:shapes="_x0000_i1037"> (6)

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

<img src="/cache/referats/2522/image032.gif" v:shapes="_x0000_i1038"> (i=1,2,…,m) (7)

Условия, что за каждой целью закрепляется не более одногосредства поражения, определяются выражением

<img src="/cache/referats/2522/image034.gif" v:shapes="_x0000_i1039"> (j=1,2,…,n) (8)

В случае знака равенства во всех выражениях (8) имеет место m=n, в противном случае m<n. Первая задачацелераспределения может быть сформулирована следующим образом.

Найти такие целые значения xij³

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

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

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

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

Таблица 3.

цели

Количество

средств

поражения

<img src="/cache/referats/2522/image005.gif" v:shapes="_x0000_s1100"> 1

x11=1

0,8*

x12=0

0,4

x13=0

0,8*

<img src="/cache/referats/2522/image038.gif" v:shapes="_x0000_s1104"><img src="/cache/referats/2522/image039.gif" v:shapes="_x0000_s1106"><img src="/cache/referats/2522/image039.gif" v:shapes="_x0000_s1107"><img src="/cache/referats/2522/image040.gif" v:shapes="_x0000_s1103"><img src="/cache/referats/2522/image038.gif" v:shapes="_x0000_s1099"> 2

x21=0

0,5

x22=0

0,1

x23=1

0,7

x31=0

0,2

x32=1

0,5*

x33=0

0,5

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

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

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

<img src="/cache/referats/2522/image042.gif" v:shapes="_x0000_i1040"> (9)

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

<img src="/cache/referats/2522/image044.gif" v:shapes="_x0000_i1041"> (10)

<img src="/cache/referats/2522/image046.gif" v:shapes="_x0000_i1042"> (11)

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

Для определения оптимального плана найдем в столбцах таблицы3 максимальные значения вероятностей и отметим их звездочками. Очевидно, что завторой целью нужно закрепить 3-е средство (x32=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<m).

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

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

<img src="/cache/referats/2522/image056.gif" v:shapes="_x0000_i1047"> (3.23)

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

x1=b

1, x2=b2,…, xn=bn; xn+1=xn+2=…=xm=0

Если все числа b

1, b1, …,bnнеотрицательны,то мы будем иметь неотрицательное решение системы (3.22), соответствующееугловой точке (вершине) многогранника неотрицательных решений, это такназываемое опорное решение.

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

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

<img src="/cache/referats/2522/image057.gif" v:shapes="_x0000_s1116"><img src="/cache/referats/2522/image058.gif" v:shapes="_x0000_s1115"><img src="/cache/referats/2522/image059.gif" v:shapes="_x0000_s1114"><img src="/cache/referats/2522/image060.gif" v:shapes="_x0000_s1110"><img src="/cache/referats/2522/image062.gif" v:shapes="_x0000_i1048"> (3.27)

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

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

<img src="/cache/referats/2522/image064.gif" v:shapes="_x0000_i1049"> (3.28)

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

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

<img src="/cache/referats/2522/image066.gif" v:shapes="_x0000_i1050"> (3.29)

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

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

Очевидно, для выполнения S-преобразования с помощью первого уравнения необходимо, чтобыкоэффициент a11¹

0 впротивном случае переменная x1в первом уравнении будет отсутствовать.

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

<img src="/cache/referats/2522/image067.gif" v:shapes="_x0000_s1118"><img src="/cache/referats/2522/image068.gif" v:shapes="_x0000_s1117"><img src="/cache/referats/2522/image070.gif" v:shapes="_x0000_i1051"> (3.30)

Если a11¹

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

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

Остальные элементы новой таблицы вычисляются по D-правилу. Например, длявычисления элемента a’ijсоединяем элемент aijна таблице (3.30) с элементом a11прямой. В результате имеем первую диагональ. Вторая диагональ получается отсоединения элементов ai1и a1j,обведенных на таблице кружками. По D-правилу имеем

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

Выполнив S-преобразованиенад таблицей (3.30), мы получим новую таблицу

<img src="/cache/referats/2522/image067.gif" v:shapes="_x0000_s1120"><img src="/cache/referats/2522/image073.gif" v:shapes="_x0000_s1119"><img src="/cache/referats/2522/image075.gif" v:shapes="_x0000_i1053"> (3.31)

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

<img src="/cache/referats/2522/image077.gif" v:shapes="_x0000_i1054"> (3.32)

Система (3.32) эквивалентна первоначальной системе (3.22),но в системе (3.32) переменная x1исключена из всех уравнений, кроме первого. Если в таблице (3.31) элемент a’22¹

0,то, приняв его за разрешающий элемент и проделав над таблицей (3.31) S-преобразование, получимновую таблицу. И в системе уравнений, соответствующей этой таблице, переменная x2 будет исключенаиз всех уравнений, кроме второго.

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

<img src="/cache/referats/2522/image079.gif" v:shapes="_x0000_s1121"><img src="/cache/referats/2522/image081.gif" v:shapes="_x0000_i1055"> (3.33)

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

<img src="/cache/referats/2522/image083.gif" v:shapes="_x0000_i1056"> (3.34)

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

еще рефераты

Еще работы по программированию, базе данных

Реферат по программированию, базе данных

Аналитический обзор книги "Программирование на языке ассемблера..."

29 Августа 2013

Реферат по программированию, базе данных

Компьютерные вирусы

29 Августа 2013

Реферат по программированию, базе данных

Математическое программирование

29 Августа 2013

Реферат по программированию, базе данных

Методы приобретения знаний в интеллектуальных системах

29 Августа 2013