РЕФЕРАТ
Тема: «Применение методов линейного программирования в
военном деле. Симплекс-метод»
курсанта 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) обеспечения потребителей, но при выборе любого из них должны быть учтены условия:
(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.
|
|
Соединения |
Запасы ГСМ на складах |
|||
|
|
|||||
|
|
|||||
| Потребность в ГСМ |
|||||
Выбор планов зависит от запасов ГСМ на складах и потребностей в нем соединений, что математически определяется выражениями:
(2 1)
(3 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 Найти такие целые значения x ij
³0 (найти такой план), удовлетворяющие условиям (7) и (8), которые обращают критерий эффективности (6) в максимум. Как видно, эта задача линейного программирования, причем транспортного типа. В отличие от задачи на перевозку здесь ищутся значения x ij
, принимающие только два возможных значения: 0 и 1. При малых m и n задачи целераспределения могут решаться путем элементарных расчетов и рассуждений. Задача. Разведкой обнаружены три равноценные цели противника. Для их уничтожения выделяется командованием три средства поражения. Известны вероятности поражения каждой цели любым средством (таблица 3). Таблица 3. Количество поражения Количество целей Требуется сформулировать задачу линейного программирования по критерию математического ожидания для данных условий и определить оптимальный план целераспределения. Решение. Критерий эффективности в этой задаче согласно формуле (6) определяем выражением: Здесь положено k 1
=k 2
=k 3
=1, т.к. все цели равноценны. Выражения (7) и (8) для условия задачи будут иметь вид: Найти такие целые положительные корни x ij
уравнений (10) и (11), при которых критерий эффективности (9) примет максимальное значение. Для определения оптимального плана найдем в столбцах таблицы 3 максимальные значения вероятностей и отметим их звездочками. Очевидно, что за второй целью нужно закрепить 3-е средство (x 32
=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 Предположим, что среди детерминантов 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.22). Одно из решений найдем, если все свободные переменные приравняем к нулю. Тогда получим: x 1
=b 1
, x 2
=b 2
, …, x n
=b n
; x n+1
=x n+2
=…=x m
=0 Если все числа b 1
, b 1
, …,b n
неотрицательны, то мы будем иметь неотрицательное решение системы (3.22), соответствующее угловой точке (вершине) многогранника неотрицательных решений, это так называемое опорное решение. Решить систему относительно базисных переменных x 1
, x 2
, …,x n
, используя свойства определителей n-го порядка, очень удобно. Мы будем решать эту систему путем последовательного исключения неизвестных. Запишем в виде таблицы коэффициенты уравнений (3.24) и элемент a 11
заключим в рамку коэффициенты от неизвестных свободных членов отделим чертой, а элемент a 11
, заключенный в рамочку, будем называть разрешающим элементом. Выпишем соответствующую таблицу для коэффициентов уравнений (3.26) Коэффициент a’ 21
равен нулю Из уравнения (3.25) следует, что На таблице (3.27) соединим элемент a 2j
c разрешающим элементом прямой линией. Рассмотрим прямоугольник, диагональю которого является проведенная линия. Эту диагональ будем называть первой диагональю. Второй диагональю является прямая, соединяющая элементы a 21
и a 1j
, обведенные кружком. Как следует из формулы (3.29), чтобы получить элемент a 2j
, нужно из произведения элементов первой диагонали вычесть произведение второй диагонали. Остальные элементы второй строки вычисляются по этому же правилу. Это правило напоминает правило вычисления детерминантов второго порядка, поэтому будем коротко называть его D-правилом. Переход от таблицы коэффициентов (3.27) к таблице (3.28), совершаемый с помощью D-правила, будем называть симплекс преобразованием или S-преобразованием одной таблицы в другую. Очевидно, для выполнения S-преобразования с помощью первого уравнения необходимо, чтобы коэффициент a 11
¹0 в противном случае переменная x 1
в первом уравнении будет отсутствовать. Если теперь возьмем первое уравнение системы (3.22) и третье и проделаем такие же вычисления, то исключим x 1
из третьего уравнения. Продолжая такие же вычисления, исключим x 1
из всех уравнений, кроме первого. Вычисления будем производить в следующем порядке. Сначала запишем таблицу коэффициентов системы (3.22) Если a 11
¹0, и мы хотим исключить x 1
с помощью первого уравнения, то принимаем элемент a 11
за разрешающий и в таблице (3.30) обводим его рамкой. Строка и столбец, в которых находится разрешающий элемент, называются соответственно разрешающей строкой и разрешающим столбцом. В таблице (3.30) это первая строка и первый столбец. Применяя симплекс преобразование, перейдем к новой таблице. В новой таблице элементы разрешающей строки переписываются без изменений. Все элементы разрешающего столбца, кроме самого разрешающего элемента заменяются нулями. Остальные элементы новой таблицы вычисляются по D-правилу. Например, для вычисления элемента a’ ij
соединяем элемент a ij
на таблице (3.30) с элементом a 11
прямой. В результате имеем первую диагональ. Вторая диагональ получается от соединения элементов a i1
и a 1j
, обведенных на таблице кружками. По D-правилу имеем При выполнении симплекс преобразования диагонали, изображенные на таблице (3.30), на самом деле проводить не нужно: они легко выделяются в уме. Выполнив S-преобразование над таблицей (3.30), мы получим новую таблицу Этой таблице соответствует система уравнений: Система (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.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
равными нулю, получим уравнения: 3x 1
=-18, откуда x 1
=6 3x 2
=-6, откуда x 2
=2 3x 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.34) и по формулам (3.35) найдем неотрицательные значения базисных переменных. Составляем отношения свободных членов b k
к положительным элементам a kj
разрешающего столбца и среди чисел Рассмотрим пример отыскания неотрицательных решений системы уравнений. Пример. Найти неотрицательное решение системы уравнений Пишем таблицу, соответствующую данной системе Пробуем разрешить эту систему относительно 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
. Полагая свободные переменные равными нулю, получим: 5x 1
=12, x 1
=12/5; 5x 2
=2, x 2
=2/5; 5x 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г. Л.В.
Канторович - экономист - внес выдающийся
вклад в экономическую науку. С его именем
связан естественнонаучный подход к
исследованию широкого круга проблем
планирования. Л.В. Канторович заложил
фундамент современной теории оптимального
планирования. Развернутому изложению
основных идей этой теории посвящена
его капитальная монография “Экономический
расчет наилучшего использования
ресурсов”
.
Стержнем этой книги является формулировка
основной задачи производственного
планирования и динамической задачи
оптимального планирования. Указанные
задачи достаточно просты, но в то же
время учитывают важнейшие черты
экономического планирования. Одно из
привлекательных качеств состоит в том,
что они базируются на схеме линейного
программирования и, следовательно, на
развитом аналитическом аппарате и
обширном наборе эффективных вычислительных
средств, часть из которых предложил сам
Леонид Витальевич. Значителен
его вклад в проблему ценообразования
- одну из коренных, затрагивающую, по
существу, все сферы функционирования
общества. Л.В. Канторович установил
связь цен и общественно-необходимых
затрат труда. Он дал определение понятия
оптимума, оптимального развития,
конкретизировав, в частности, что следует
понимать под максимальным удовлетворением
потребностей членов общества. Из его
положения о неразрывности плана и цен
вытекает зависимость общественно-необходимых
затрат труда от поставленных целей
общества. Таким
образом, цели общества, оптимальный
план и цены составляют одно неразрывное
целое. Им указаны конкретные условия,
при которых объективно обусловленные
оценки оптимального плана совпадают с
полными (прямыми и сопряженными) затратами
труда. Определение перспектив экономики,
наличие гигантских “естественных
монополий” заставляет сохранить для
них расчет, по крайней мере, опорных
цен, согласованных и взаимно, и с
интересами других отраслей экономики. Математические
модели получили отражение в некоторых
курсах политической экономии. В работах
Л.В. Канторовича исследовался ряд
основных проблем экономической теории
и практики хозяйствования. Указывая на
недостатки действовавшей экономической
системы, Л.В. Канторович подчеркивал,
что система экономических показателей
должна быть единой, построена по единому
принципу. В связи с этим значительную
часть своих работ в этой области Леонид
Витальевич посвятил разработке и анализу
конкретных экономических показателей. В
работах самого Л.В. Канторовича особое
внимание было уделено оценке земельных
ресурсов и воды, учету этих показателей
в (заготовительных) ценах на
сельскохозяйственную продукцию.
Предложены оригинальные подходы к их
расчету (сочетание метода наименьших
квадратов и линейного программирования).
На этой основе были даны рекомендации
по улучшению системы экономических
показателей и расчетов в сельском
хозяйстве. Значение предложенных им
принципов расчета в складывающейся
экономической системе только возрастает. В
работах Л.В. Канторовича вскрывается
сущность понятия показателя эффективности
капиталовложений, показывается его
роль в экономических расчетах принятия
решений, предлагается методика определения
величины этого нормативного показателя.
Таким образом, Л.В. Канторович дал
убедительное научное обоснование
необходимости применения норматива
эффективности и на основе оптимизационного
подхода дал объективный путь его расчета. В
работе “Амортизационные платежи при
оптимальном использовании оборудования”
(1965) Л.В. Канторовичем была вскрыта
сущность понятия амортизации. Он показал,
как можно повысить эффективность
использования оборудования, разделив
амортизационные платежи на два типа, и
с помощью остроумной математической
модели указал, как определить численную
величину коэффициента амортизационных
отчислений. Это изменение позволило
сделать ряд принципиальных выводов о
необходимости корректировки принятой
методики расчета амортизации. Специальный
интерес проявлял Леонид Витальевич к
проблемам транспорта. Еще в его первых
экономических работах были даны общий
анализ транспортной задачи и метод
потенциалов для ее решения. Этот метод
широко использовался на транспорте
(железнодорожном, автомобильном, морском,
воздушном) и в органах централизованного
снабжения для рационального прикрепления
и рациональной организации перевозок.
Он, безусловно, сохраняет свое значение
и сейчас наряду с широко используемыми
методами диспетчерского управления и
расчетами маршрутов. В
работах “Об
использовании математических моделей
в ценообразовании на новую технику”
(1968) и “Математико-экономический
анализ плановых решений и экономические
условия их реализации
”
(1971) Л.В. Канторович исследовал проблему
эффективной работы транспорта с
экономической точки зрения, показал,
каковы должны быть транспортные тарифы
в зависимости от вида транспорта, груза,
расстояний и т. д. В ряде работ им
рассматривались и вопросы комплексной
транспортной системы - взаимосвязь
транспорта с другими отраслями народного
хозяйства и распределение перевозок
между видами транспорта с учетом
экономичности и в особенности энергозатрат.
Эти работы сохраняют свое значение и
сейчас. Помимо
проблем народнохозяйственного
планирования, Л.В. Канторович рассмотрел
вопросы, относящиеся к отраслевому
планированию. Наиболее простой и часто
используемой является предложенная им
модель, базирующаяся на транспортной
задаче. На ряд более сложных моделей, в
частности производственно-транспортной,
динамической, декомпозиционной, им
указано в работах, посвященных текущему
и перспективному отраслевому планированию
(“Возможности применения математических
методов в вопросах производственного
планирования”, 1958) и др. Эти вопросы
нашли отражение в исследованиях по
отраслевым АСУ. Большое
внимание Леонид Витальевич уделял
вопросам рационального использования
труда. Им было предложено введение
платежей предприятий за использование
труда дифференцированных по профессиям,
половозрастным признакам и территории.
Он указывал также на возможности
научного, количественного подхода к
социальным проблемам, вопросам
совершенствования сферы услуг и др.
Вопросы экономического стимулирования
рационального использования трудовых
ресурсов остаются актуальными и сейчас. В
течение ряда лет и особенно в последние
годы Л.В. Канторовича интересовали
проблемы эффективности технического
прогресса, в частности вопросы внедрения
в производство новой техники. Особый
интерес представляет обоснование
предложения об установлении двух уровней
цен на принципиально новую продукцию
в первые годы ее выпуска. Важное значение
имел также вывод о необходимости более
высоко оценивать вклад в национальный
доход технического прогресса и науки,
чем это получалось по принятым тогда
методам расчета (“Ценообразование и
технический прогресс”, 1979). Л.В.
Канторович уделял большое внимание
внедрению разработанных им методов в
экономическую практику. В первую очередь
в этой связи следует отметить цикл
работ, посвященных методам рационального
раскроя материалов, начатый Леонидом
Витальевичем еще в 1939 - 1942 гг. В 1948 - 1950
гг. эти методы были внедрены на
Ленинградском вагоностроительном
заводе имени Егорова, на Кировском
заводе и распространены впоследствии
на некоторых других предприятиях. Более
широкому распространению методов
рационального раскроя способствовал
ряд проведенных по инициативе Л.В.
Канторовича совещаний. С
1964 г. по предложению Леонида Витальевича
проводилась большая работа по внедрению
системных методов расчета оптимальной
загрузки прокатных станов в масштабах
всей страны. Являясь
членом Государственного комитета по
науке и технике, Л.В. Канторович вел
большую организационную работу,
направленную на совершенствование
методов планирования и управления
народным хозяйством. Он возглавлял
Научный совет ГКНТ по использованию
оптимизационных расчетов, состоял
членом многих ведомственных советов и
комиссий (по ценообразованию, транспорту
и др.). Вклад Леонида Витальевича в
исследование проблемы эффективности
производства и, в частности, проблемы
эффективности капитальных вложений
исключительно велик. «за вклад в теорию оптимального распределения ресурсов»
Русский экономист Леонид Витальевич Канторович родился в 1912 г. в Санкт-Петербурге, Россия. Русская революция началась, когда ему было пять лет, во время гражданской войны его семья бежала на год в Белоруссию. В 1922 г. умер его отец, Виталий Канторович, оставив сына на воспитание матери, урожденной Паулины Сакс.
К. проявлял интерес к естественным наукам задолго до того, как он в 1926 г. в возрасте четырнадцати лет поступил в Ленинградский университет. Здесь он изучает не только естественные дисциплины, но и политэкономию, современную историю, математику. Его склонность к математике становится определяющей в работе по теории рядов, которую он представил на первом Всесоюзном математическом конгрессе в 1930 г. Закончив в том же году учебу, он остается в Ленинградском университете на преподавательской работе и продолжает свои исследования на кафедре математики. К 1934 г. он становится профессором, а годом позже, когда была восстановлена система академических степеней, получает докторскую степень.
В 30-е гг., в период интенсивного экономического и индустриального развития Советского Союза, К. был в авангарде математических исследований и стремился применить свои теоретические, разработки в практике растущей советской экономики. Такая возможность представилась в 1938 г., когда он был назначен консультантом в лабораторию фанерной фабрики. Перед ним была поставлена задача разработать такой метод распределения ресурсов, который мог бы максимизировать производительность оборудования, и К., сформулировав проблему с помощью математических терминов, произвел максимизацию линейной функции, подверженной большому количеству ограничителей. Не имея чистого экономического образования, он тем не менее знал, что максимизация при многочисленных ограничениях – это одна из основных экономических проблем и что метод, облегчающий планирование на фанерных фабриках, может быть использован во многих других производствах, будь то определение оптимального использования посевных площадей или наиболее эффективное распределение потоков транспорта.
Метод К., разработанный для решения проблем, связанных с производством фанеры, и известный сегодня как метод линейного программирования, нашел широкое экономическое применение во всем мире. В работе «Математические методы организации и планирования производства», опубликованной в 1939 г., К. показал, что все экономические проблемы распределения могут рассматриваться как проблемы максимизации при многочисленных ограничителях, следовательно, могут быть решены с помощью линейного программирования.
В случае с производством фанеры он представил переменную, подлежащую максимизации, в виде суммы стоимостей продукции, выпускаемой всеми машинами. Ограничители были представлены уравнениями, которые устанавливали соотношение между количеством каждого из расходуемых факторов производства (например, древесины, электроэнергии, рабочего времени) и количеством продукции, выпускаемой каждой из машин, где величина любой из затрат не должна превышать имеющуюся в распоряжении сумму.
Затем К. ввел новые переменные (разрешающие мультипликаторы) как коэффициенты к каждому из факторов производства в ограничительных уравнениях и показал, что значения как переменной затрачиваемых факторов, так и переменной выпускаемой продукции могут быть легко определены, если известны значения мультипликаторов. Затем он представил экономическую интерпретацию этих мультипликаторов, показав, что они, в сущности, представляют собой предельные стоимости (или «скрытые цены») ограничивающих факторов; следовательно, они аналогичны повышенной цене каждого из факторов производства в режиме полностью конкурентного рынка.
И хотя с тех пор разрабатывались более совершенные компьютерные методики для определения значений мультипликаторов (К. использовал метод последовательного приближения), его первоначальное понимание экономического и математического смысла мультипликаторов заложило основу для всех последующих работ в этой области в Советском Союзе. Впоследствии сходная методология была независимо разработана на Западе Тьяллингом Ч. Купмансом и другими экономистами.
Даже в тяжелые годы второй мировой войны, когда К. занимал должность профессора в Военно-морской инженерной академии в блокадном Ленинграде, он сумел создать значительное исследование «О перемещении масс» (1942). В этой работе он использовал линейное программирование для планирования оптимального размещения потребительских и производственных факторов.
Продолжая работать в Ленинградском университете, К. одновременно возглавил отдел приближенных методов в Институте математики АН СССР в Ленинграде. В последующие несколько лет он способствовал развитию новых математических методов планирования для советской экономики. В 1951 г. он (совместно с математиком, специалистом в области геометрии В.А. Залгаллером) опубликовал книгу, описывающую их работу по использованию линейного программирования для повышения эффективности транспортного строительства в Ленинграде. Через восемь лет он опубликовал самую, видимо, известную свою работу «Экономический расчет наилучшего использования ресурсов». В ней он сделал далеко идущие выводы по идеальной организации социалистической экономики для достижения высокой эффективности в использовании ресурсов. В особенности он рекомендовал шире использовать скрытые цены при распределении ресурсов по Союзу и даже применять процентную ставку для выражения скрытой цены времени при планировании капиталовложений.
Хотя некоторые советские ученые с опаской относились к этим новым методам планирования, постепенно методы К. были приняты советской экономикой. В 1949 г. он был удостоен Сталинской премии за работу в области математики, в 1958 г. избран членом-корреспондентом Академии наук СССР. Шестью годами позже он стал академиком. В 1960 г., переехав в Новосибирск, где был расположен самый передовой в СССР компьютерный центр, он стал руководителем отдела экономико-математических методов в Сибирском отделении АН СССР. Вместе со своими коллегами, экономистами-математиками В.В. Новожиловым и В.С. Немчиновым, К. стал лауреатом Ленинской премии в 1965 г., а в 1967 г. был награжден орденом Ленина. В 1971 г. он становится руководителем лаборатории в Институте управления народным хозяйством в Москве.
Премия памяти Нобеля 1975 г. по экономике была присуждена совместно К. и Тьяллингу Ч. Купмансу «за вклад в теорию оптимального распределения ресурсов». В своей речи на церемонии презентации представитель Шведской королевской академии наук Рагнар Бентцель отмечал очевидность того, о чем свидетельствовали работы двух лауреатов, – «основные экономические проблемы могут изучаться в чисто научном плане, независимо от политической организации общества, в котором они исследуются». Работы Купманса и К. по линейному программированию тесно соприкасались, а американский ученый подготовил в 1939 г. первую публикацию книги советского ученого на английском языке. В своей Нобелевской лекции «Математика в экономике: достижения, трудности, перспективы» К. говорил о «проблемах и опыте плановой экономики, особенно советской экономики».
В следующем году К. стал директором Института системных исследований АН СССР. Проводя собственные исследования, он в то же время поддерживал и обучил целое поколение советских экономистов.
В 1938 г. К. женился на Наталье Ильиной, враче по профессии. Их дети – сын и дочь – стали экономистами. К. скончался 7 апреля 1986 г. в возрасте 74 лет.
Кроме Нобелевской премии и наград, полученных в СССР, К. были присуждены почетные степени университетами Глазго, Гренобля, Ниццы, Хельсинки и Парижа; он был членом Американской академии наук и искусств.
До середины ХХ в. экономисты-теоретики игнорировали математические модели исследования. Однако, несмотря на притеснения, математики продолжали работать и достигли блестящих результатов. Среди них - представители математической школы Л. Канторович и Т.-Ч. Купманс. Канторович (Kantorovich) Леонид Витальевич (1912-1986) - советский экономист, лауреат Нобелевской премии (1975). Теория оптимального распределения ресурсов
- теория, которая предусматривает формулирование статистической и динамической моделей текущего и перспективного планирования использования ресурсов на базе новых математических подходов в сфере системного построения экономических показателей, используемых для анализа ценообразования, эффективности капитальных вложений. Впервые основы теории оптимального распределения ресурсов он изложил в работе «Математические методы организации и планирования производства» (1939). В ней он представил принципиально новый класс экстремальных задач с ограничениями, разработав эффективный метод их решения. Именно в это время ученый сформулировал задачу составления плана и системы цен как взаимозависимых компонентов неделимой двойственности. Ведь время невозможно одновременно минимизировать издержки и максимизировать результаты. Одновременно эти два подхода взаимосвязаны: если найдем оптимальную схему перевозок, то ей соответствует определенная система цен. Если определим оптимальные значения цен, то сравнительно легко получить схему перевозок, что соответствует требованиям оптимальности. Основой этой теории является метод линейного программирования. Линейное программирование - решение линейных уравнений (уравнений первой степени) путем сложения программ и внедрения разных методов их последовательного решения, что существенно облегчает расчеты и достижение результатов. Л. Канторович обосновал экономическую сущность предлагаемых им решающих множителей. Они, собственно, являются предельными стоимостями ограничивающих факторов. То есть это объективные цены каждого из факторов производства относительно условий конкурентного рынка. Для решения задачи на оптимальность ученый использовал метод последовательных приближений, последовательного сопоставления вариантов с выбором наилучшего в соответствии с условиями задачи. Задачи линейного программирования были известны еще в конце ХVIII в. Однако начали решать их только после публикаций работ Л. Канторовича. В США исследования по линейному программированию начались только в конце 40-х годов ХХ в. Транспортная задача Хичкока и симплекс-метод Данцига, которые близки по характеру к методу решения задач линейного программирования Канторовича, были разработаны на десятилетие позднее. Целостность мышления проявлялась во всем творчестве Канторовича. Идеи линейного программирования были тесно связаны с его методологическими установками в области математики. В середине 1930 годов центральное место в математических исследованиях Канторовича занимал функциональный анализ. Труды Канторовича заложили фундамент теории оптимального планирования социалистической экономики, вплоть до конца 80-х годов широко используемой в практике планирования экономического развития в СССР, а также в других социалистических странах. Основные идеи теории оптимального планирования изложены в монографии "Экономический расчет наилучшего использования ресурсов" (1959, 1960), являющейся наиболее известной работой ученого. Стержнем этой книги являлась формулировка основной задачи производственного планирования и динамической задачи оптимального планирования. Указанные задачи формулировались достаточно просто, но они учитывали основные черты планирования в советской экономике. Похожая информация: Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны. Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Рязанский государственный университет имени С.А. Есенина Контрольная работа по предмету: История экономических учений на тему: Л.В. Канторович - родоначальник теории линейного программирования (теории оптимального использования ресурсов). Выполнила: Чернова Н.В. Рязань 2014 г. Введение 1.2 Вклад в науку 1.3 Научные работы Заключение Список использованных источников Введение В этом реферате я напишу о деятельности Леонида Витальевича Канторовича, выдающегося ученого ХХ века. О его борьбе за признание своих экономико-математических теорий, о начальном этапе истории линейного программирования, о зарождении новой области математической деятельности, связанной с экономическими приложениями, называемой у нас, то исследованием операций, то математической экономикой, то экономической кибернетикой и т. п., о ее месте и связях с современным математическим ландшафтом. 1. Леонид Витальевич Канторович 1.1 Биография Л.В. Канторовича Леонид Витальевич Канторович (1912--1986) родился в Санкт-Петербурге в семье врача. Его выдающиеся способности проявились рано -- в 14 лет он поступил в Ленинградский государственный университет. Закончив ЛГУ за 4 года, он поступил в аспирантуру. В 1932 г. он становится доцентом, а в 1935 г. -- профессором ЛГУ. В 1935 г. ему присвоено звание доктора физико-математических наук без защиты диссертации. В 1958 г. он избран членом-корреспондентом АН СССР по экономике, а в 1964 г. -- академиком. За разработку метода линейного программирования и экономических моделей удостоен в 1965 году вместе с академиком В. С. Немчиновым и профессором В. В. Новожиловым Ленинской премии. С 1971 года работал в Москве, в институте управления народным хозяйством Государственного комитета Совета Министров СССР по науке и технике. 1975 год -Нобелевская премия по экономике (совместно с Т. Купмансом «за вклад в теорию оптимального распределения ресурсов»). С 1976 работал во ВНИИСИ ГКНТ и АН СССР, ныне Институт системного анализа РАН. Награждён 2 орденами Ленина (1967, 1982), 3 орденами Трудового Красного Знамени (1949, 1953, 1975), орденом Отечественной войны 1-й степени (1985), орденом «Знак Почёта» (1944). Почётный доктор многих университетов мира. 1.2 Вклад в науку Научное наследие Л.В. Канторовича огромно. Его исследования в области функционального анализа, вычислительной математики, теории экстремальных задач, дескриптивной теории функций оказали фундаментальное влияние на становление и развитие названных дисциплин. Л.В. Канторович по праву входит в число основоположников современного экономико-математического направления. Л.В. Канторович -- автор более трехсот научных работ, которые при подготовке аннотированной библиографии его сочинений он сам предложил распределить по следующим девяти разделам: дескриптивная теория функций и теория множеств; конструктивная теория функций; приближенные методы анализа; функциональный анализ; функциональный анализ и прикладная математика; линейное программирование; вычислительная техника и программирование; оптимальное планирование и оптимальные цены; экономические проблемы плановой экономики. Столь впечатляющее многообразие направлений исследований объединяется не только личностью Л.В. Канторовича, но и его методическими установками. Он всегда подчеркивал внутреннее единство науки, взаимопроникновение идей и методов, необходимых для решения самых разнообразных теоретических и прикладных проблем математики и экономики. Еще одной характерной чертой его творчества является тесная взаимосвязь с наиболее трудными проблемами и самыми перспективными идеями математики и экономики того времени. Осветить творчество Леонида Витальевича кратко невозможно. Сам он выделял из сделанного в науке две вещи: линейное программирование и K-пространства. 1.3 Научные работы Л.В. Канторовича Научные работы: Первые научные результаты получены в дескриптивной теории функций и множеств и, в частности, по проективным множествам. В функциональном анализе ввёл и изучил класс полуупорядоченных пространств (К-пространств). Выдвинул эвристический принцип, состоящий в том, что элементы К-пространств суть обобщённые числа. Этот принцип был обоснован в 1970-е годы в рамках математической логики. Булевозначный анализ установил, что пространства Канторовича представляют новые нестандартные модели вещественной прямой. Впервые применил функциональный анализ к вычислительной математике. Развил общую теорию приближённых методов, построил эффективные методы решения операторных уравнений (в том числе метод наискорейшего спуска и метод Ньютона для таких уравнений). В 1939-40 положил начало линейному программированию и его обобщениям. канторович линейный программирование Развил идею оптимальности в экономике. Установил взаимозависимость оптимальных цен и оптимальных производственных и управленческих решений. Каждое оптимальное решение взаимосвязано с оптимальной системой цен. Канторович -- представитель петербургской математической школы П.Л. Чебышёва, ученик Г.М. Фихтенгольца и В.И. Смирнова. Канторович разделял и развивал взгляды П.Л. Чебышева на математику как на единую дисциплину, все разделы которой взаимосвязаны, взаимозависимы и играют особую роль в развитии науки, техники, технологии и производства. Канторович выдвигал тезис взаимопроникновения математики и экономики и стремился к синтезу гуманитарных и точных технологий знания. Творчество Канторовича стало образцом научного служения, базирующегося на универсализации математического мышления. 2. Зарождение линейного программирования Линейное программирование изучают десятки тысяч людей во всем мире. Под этим термином скрывается колоссальный раздел науки, посвященный линейным оптимизационным моделям. Иначе говоря, линейное программирование -- это наука о теоретическом и численном анализе и решении задач, в которых требуется найти оптимальное значение, т. е. максимум или минимум, некоторой системы показателей в процессе, поведение и состояние которого описывается той или иной системой линейных неравенств. Одним из наиболее значительных и ярких достижений в области экономико-математических исследований было открытие Леонидом Витальевичем Канторовичем метода линейного программирования. Линейное программирование -- решение линейных уравнений (уравнений первой степени) посредством составления программ и применения различных методов их последовательного решения, существенно облегчающих расчеты и достижение искомых результатов. Сам термин «линейное программирование» был предложен в 1951 году американским экономистом Т. Купмансом. За разработку метода линейного программирования или, как сказано в дипломе Шведской академии наук, за «вклад в теорию оптимального распределения ресурсов» Л.В. Канторович был удостоен Нобелевской премии по экономике (1975). Премия была присуждена ему совместно с американским экономистом Тьяллингом Чарльзом Купмансом, который несколько позже, независимо от Канторовича, предложил сходную методологию. Разработка линейного программирования началась с поиска решения практической задачи. К Канторовичу обратились инженеры фанерного треста с просьбой найти эффективный способ распределения ресурсов, обеспечивающий наиболее высокую производительность оборудования. Работники предприятия ломали голову над тем, как при пяти станках и восьми видах сырья обеспечить оптимальный вариант выпуска фанеры. Иными словами, нужно было найти решение конкретной технико-экономической задачи с целевой функцией («функционалом») максимизировать выпуск готовой продукции. Заслуга Канторовича состоит в том, что он предложил математический метод выбора оптимального варианта. Решая частную задачу наиболее рациональной загрузки оборудования, ученый разработал метод, получивший название метода линейного программирования. По сути дела, он открыл новый раздел математики, получивший широкое распространение в экономической практике, способствовавший развитию и использованию электронно-вычислительной техники. С оптимальным планом любой линейной программы автоматически связаны оптимальные цены или «объективно обусловленные оценки». Последнее громоздкое словосочетание Леонид Витальевич выбрал из тактических соображений для повышения «критикоустойчивости» термина. Взаимозависимость оптимальных решений и оптимальных цен -- такова краткая суть экономического открытия Л.В. Канторовича. В задаче по оптимизации выпуска фанеры Канторович представил переменную, которую следовало максимизировать в виде суммы стоимостей продукции, производимой всеми станками. Ограничители были представлены в форме уравнений, устанавливающих соотношения между всеми затрачиваемыми в производстве факторами (древесиной, клеем, электроэнергией, рабочим временем) и количеством выпускаемой продукции (фанеры) на каждом из станков. Для показателей факторов производства были введены коэффициенты, названные разрешающими множителями, или мультипликаторами. С их помощью разрешается поставленная задача. Если известны значения разрешающих множителей, то искомые величины, в частности, оптимальный объем выпускаемой продукции, могут быть сравнительно легко найдены. Канторович обосновал экономический смысл предложенных им коэффициентов (разрешающих множителей). Они представляют собой не что иное, как предельные стоимости ограничивающих факторов. Иначе говоря, это объективно значимые цены каждого из факторов производства применительно к условиям конкурентного рынка. Для решения задачи на оптимум Канторович использовал метод последовательных приближений, метод последовательного сопоставления вариантов с выбором наилучшего в соответствии с условиями задачи. Допустим, требуется решить транспортную задачу, обосновать наиболее рациональное распределение грузопотоков. Для примера, всего нужно перевести 180т груза из трех источников к трем потребителям, общий спрос которых также равен 180 т. Сложность в том, что груз распределен неравномерно: у одного поставщика имеется 50 т, у другого -- 60 т, у третьего -- 80 т. Также неравнозначен спрос потребителей: он составляет соответственно 40, 85 и 55 т. Неодинаковы и расстояния -- плечи перевозки грузов -- от 1 до 6 км. Задача заключается в том, чтобы составить такой план перевозок, который отвечал бы требованию минимизации грузооборота (минимальному количеству тонно-километров). В повседневной практике менеджеры могут заняться монотонной работой по длительному перебору возможных вариантов. Постепенно они смогут «пройти» от плана перевозок, скажем, в 750 т/км к плану в 655 т/км. Поиск потребует массу усилий, значительного количества расчетов. Главное же -- трудно установить, какой из предлагаемых вариантов является оптимальным. Допустим, найден вариант плана с грузооборотом в 575 т/км. Но остается неизвестным, нет ли еще одного или нескольких более выгодных вариантов плана, требующих меньших затрат. Задача становится совсем неразрешимой, если перейти от сравнительно простой схемы к составлению варианта перевозок одного или нескольких продуктов (угля, цемента, стройматериалов) в масштабе региона или страны. Даже в случае укрупнения, агрегирования исходных показателей расчеты и сопоставления вариантов потребуют проведения такого количества операций, для осуществления которых придется привлечь чуть ли не все население Украины. Метод линейного программирования позволяет найти оптимальное решение. Линейным оно называется потому, что основывается на решении линейных уравнений. Неизвестные в них только первой степени; ни одно неизвестное не перемножается на другое неизвестное. Такие уравнения отражают зависимости, которые могут быть изображены на графике прямыми линиями. Несколько иной целевой критерий в задаче о диете (кормовом рационе). Задача сводится к поиску оптимального рациона для кормления скотины или птицы. При постоянном изменении рыночных цен на корма фермеры подбирают оптимальный рацион при минимуме затрат, производя соответствующие расчеты на компьютере. Впервые работа, в которой излагалось существо предложенного Канторовичем метода, была опубликована в 1939 г. под названием «Математические методы организации планирования производства». Продолжая исследования, ученый разрабатывает общую теорию рационального использования ресурсов. В период Великой Отечественной войны, будучи профессором Военно-морской инженерной академии в блокадном Ленинграде, Канторович, опираясь на метод линейного программирования, обосновывает оптимальное размещение производственных и потребительских факторов. В 1942 г. он подготовил книгу «Экономический расчет наиболее целесообразного использования ресурсов», которая в тот период, к сожалению, не была опубликована. Прошло 17 лет, прежде чем Леонид Витальевич смог увидеть опубликованным свой фундаментальный труд «Экономический расчет наилучшего использования ресурсов». Это случилось через 6 лет после смерти Сталина. К тому времени линейное программирование как модная новинка в период оттепели стало проникать к нам с Запада. И тогда вдруг выяснилось, что ту самую теорему двойственности, которую только что самостоятельно доказали американцы, профессор Канторович доказал еще в 30-е годы. Леонид Витальевич и его ученики с энтузиазмом вновь принялись за решение экстремальных экономических задач, но очень скоро почувствовали, что реально в советской жизни ничего не изменилось. То на заводе «Москвич» не внедряют экономичную схему раскроя дорогого французского кузовного металла - из-за кампании по сокращению рабочих-подсобников, то кто-то, внедрив новый метод и получив изрядный прирост готовой продукции, в итоге лишился премии, ибо сорвал план по сдаче металлолома. Когда казалось, что трясина засасывает, и надежд на использование объективно-обусловленных оценок нет, Леонид Витальевич отводил душу, сочиняя басни. Теперь мы понимаем, что в тех условиях, при той системе принятия решений, все попытки Канторовича внедрить в жизнь новую экономику были обречены. «Объективные оценки» требовали отказа от жестких директив, а это порождало опасность разрушения самого здания социалистической экономики. В этой книге, как отмечали члены Научного совета по применению математики в научных исследованиях и планировании, представлен углубленный анализ идей линейного программирования, разработанного автором ранее, и вместе с тем впервые ставится проблема разработки оптимального плана всего народного хозяйства как математической модели. Несомненной заслугой Канторовича является выявление двойственных оценок в задачах линейного программирования. Нельзя одно временно минимизировать затраты и максимизировать результаты. Одно противоречит другому. Вместе с тем оба этих подхода взаимосвязаны. Если, скажем, найдена оптимальная схема перевозок, то ей соответствует определенная система цен. Если найдены оптимальные значения цен, то сравнительно нетрудно получить схему перевозок, отвечающую требованию оптимальности. Для любой задачи линейного программирования существует сопряженная ей, или двойственная задача. Если прямая задача заключается в минимизации целевой функции, то двойственная -- в максимизации. Двойственные оценки дают принципиальную возможность соизмерять не только ценовые, затратные показатели, но и полезности. При этом двойственные, взаимосвязанные оценки соответствуют конкретным условиям. Если изменяются условия, меняются оценки. В известной мере поиск оптимума -- это определение общественно необходимых затрат, учитывающих, с одной стороны, трудовые, стоимостные затраты, а с другой - общественные потребности, полезности продукта для потребителей. При непосредственном участии Канторовича и его ближайших коллег - В.В. Новожилова (автора идеи продуктово-трудового баланса) и В.С. Немчинова (обосновавшего глобальный критерий функционирования экономики) формировалась отечественная экономико-математическая школа. В Москве и Ленинграде Канторовичу становилось все более неуютно. И главное, до предела сузилась возможность продуктивно работать. Конечно же, это его угнетало. И потому не искатель приключений и не авантюрист по натуре, он с радостью принял предложение университетского однокурсника, академика Соболева, - покинуть столичные болота и отправиться создавать новый научных центр там, куда раньше таких, как он, ссылали. Новосибирский Академгородок в те годы стал действительно оазисом. Науки расцветали в нем свободно и невероятно энергично, отчасти потому, что там царила молодежь, не только по возрасту, но и по духу. Заключение На первый взгляд, теории Л.В. Канторовича были, как он сам говорил, приспособлены к плановой экономике. Но это лишь внешняя сторона дела. Главное - учет скрытых параметров (рента), единый подход к ограничениям (труд - всего лишь одно из них) и все, что отсюда вытекает - делают его экономические приложения универсальными и необходимыми сейчас. Вообще, главный итог великого эксперимента Канторовича в том, что он подошел к экономическим проблемам вооруженный самыми современными для тех лет математическими средствами, и творчески применял их. Это не значит, что его выводы будут полностью работать и сегодня, но это, безусловно, значит, и в этом отношении Л.В. Канторович был, возможно, первым, что талант математика может в корне переустроить и преобразовать экономическую мысль. Научный вклад Л. Канторовича - это знаменитые научные школы в области функционального анализа, вычислительной математики, математической экономики и оптимального планирования народного хозяйства. Открытое им математическое программирование широко используется для решения равных задач в экономике. Метод линейного программирования впервые позволил точно сформулировать важное современное экономико-математическое понятие "оптимальность". Л. Канторович и его коллеги разработали систему оптимального функционирования экономики (СОФЭ), сформировали модели эффективного распределения и оценки ресурсов. Он дал ей экономическое объяснение и показал ее значение в хозяйственном управлении. Это был научно обоснованный подход к вычислению числового значения единого народнохозяйственного экономического показателя эффективности использования капитальных вложений, который намного опередил свой час. Список литературы и использованных источников 1. История экономических учений: Учебное пособие /Под ред. А.Г. Худокормова. - М.: Изд-во МГУ, 1994. - Ч. II, гл. 30. 2. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. - М.: Изд-во АН СССР, 1959. 3. Капустин В.Ф., Шабалин Г.В. Л.В. Канторович и экономико-математические исследования: итоги, проблемы, перспективы // Вестник Санкт-Петербургского университета. Сер. 5. Экономика. 1996. Вып. 2. 4. Пезенти А. Очерки политической экономии капитализма. В 2 т. - М.: Прогресс, 1976. Т. II , гл. 14. 5. Шаталин С.С. Функционирование экономики развитого социализма. - М.: Изд-во МГУ, 1982. 6. Шухов Н.С. Ценность и стоимость. - М.: Изд-во стандартов, 1994. - Ч. 2, вып. 1, гл. 8. Размещено на Allbest.ru Изучение научной деятельности Л.В. Канторовича - ученого ХХ в., чьи исследования в области функционального анализа, вычислительной математики, теории экстремальных задач, дескриптивной теории функций оказали фундаментальное влияние на развитие науки. реферат , добавлен 02.04.2012 Математика в Древнем Вавилоне и Древнем Египте. Теория воспроизводства К. Маркса. Основы экономико-математических моделей. История зарождения линейного программирования. Методы множителей Лагранжа. Исследование математических принципов теории богатства. реферат , добавлен 08.01.2014 Решение формализованной задачи линейного программирования графически и с помощью Excel. Получение максимальной прибыли и план выпуска продукции. План перевозок с минимальными расходами. Межотраслевая балансовая модель. Составление системы ограничений. контрольная работа , добавлен 08.04.2010 Разработка оптимального по прибыли плана выпуска запчастей двух видов. Построение математической модели табличным симплекс-методом и в Excel. Установление изменения оптимальной прибыли при увеличении запасов каждого из дефицитных ресурсов на 5 единиц. практическая работа , добавлен 24.05.2016 Эволюция экономических теорий в контексте межрегиональной конкуренции. Этапы развития теории межрегиональной конкуренции. Вклад различных научных теорий в ее формирование. Особенности теории межрегиональной конкуренции в современном ее представлении. статья , добавлен 12.09.2011 Причины развития экономических связей между странами. Сущность основных неотехнологических теорий: меркантилистской теории; теории соотношения факторов производства; парадокса Леонтьева; теории модели прямых инвестиций; теории передачи технологии. контрольная работа , добавлен 17.10.2010 Оценка подвижного состава и доли имеющихся транспортных средств. Расчет спроса на бытовую технику в регионах, на основании маркетинговых данных. Распределение транспортных потоков продукции с помощью математических методов линейного программирования. курсовая работа , добавлен 04.12.2014 Субъективистский, неопозитивно-эмпирический, рационалистический, диалектико-материалистический подходы к изучению экономических явлений. Методы теории вероятности и математической статистики, использование экономико-математического моделирования. курсовая работа , добавлен 02.03.2014 История развития российской экономики в именах людей, внесших значительный вклад в развитие экономической науки, первыми разработавших различные методики, теории, стратегии в различных областях экономики: Л.В. Канторович, Н.Д. Кондратьев, А.В. Чаянов. реферат , добавлен 28.02.2011 Особенности зарождения и развития экономической теории. Обобщение основных методов экономической теории: диалектический метод, методы абстракции, дедукции и индукции, допущения "при прочих равных условиях", анализа и синтеза. Анализ метода экономики.
Средства поражения
1
2
(10)
(11)
(3.22)
(3.23)
(3.27)
(3.28)
(3.30)
(3.31)
(3.32)
(3.33)
(3.34)
(3.36)
выбираем наименьшее значение. Если наименьшее значение достигается при k=i, то i-номер разрешающей строки, а разрешающим элементом будет a ij
.
Особенности жизни, деятельности, вклада в науку, экономико-математических теорий Л.В. Канторовича. Анализ начального этапа истории линейного программирования, зарождения новой области математической деятельности, связанной с экономическими приложениями.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Подобные документы