Реферат: Компьютерное математическое моделирование в экономике
МИНИСТЕРСТВООБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИШадринскийГосударственный Педагогический институтКОМПЬЮТЕРНОЕ МАТЕМАТИЧЕСКОЕМОДЕЛИРОВАНИЕ В ЭКОНОМИКЕ.
Курсоваяработа.
Выполнили:
Студентки201 гр.
БлагодареваЮлия Григорьевна
РеутоваЕлена Александровна
Руководитель:
ПайвинаЮлия Васильевна
Шадринск,2003 г.
Оглавление
Введение…………………………………………………….….……..3
1. Постановка задачи линейного программирования….…...4
2. Симплекс-метод……………………………………………14
3. Контрольные вопросы и задания…………………………21
Заключение……………………………………………….…………..24Литература…………………………………………………….………25
ВведениеВ последние годы мы особенно отчетливо ощутили, что нет ничего важнее дляобщества, чем здоровая экономика. Научное исследование основ функционированияэкономики – сложная и интересная деятельность. Математические методы в нейиграют возрастающую с каждым десятилетием роль, а реализация возникающих приэтом математических моделей и получение практически важных результатовневозможны без ЭВМ.
ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГОПРОГРАММИРОВАНИЯ
В данном параграфе рассматривается лишь один изразделов — оптимальное планирование — и внутри него одна из моделей, такназываемое, линейное программирование. Это связано с относительной простотой иясностью как содержательной постановки соответствующих задач, так и методоврешения. О таких интересных, но более сложных проблемах, как выпуклоепрограммирование, динамическое программирование, теория игр мы лишь упомянем,отсылая читателей за подробностями к специальной литературе. Отметим еще, чтотермин «программирование» в названии этих разделов теории оптимальногопланирования весьма условен, связан с историческими обстоятельствами и кпрограммированию в общепринятом сейчас смысле прямого отношения не имеет.
Общеизвестно, сколь важно для решения экономическихзадач планирование — как при рыночной, так и при плановой экономике. Обычно длярешения экономической проблемы существует много способов (стратегий), отнюдьне равноценных по затратам финансов, людских ресурсов, времени исполнения, атакже по достигаемым результатам. Наилучший из способов (по отношению квыбранному критерию — одному или нескольким) называют оптимальным. Приведемпростейший пример такого рода задач.
Пример 1. На некотором предприятии могутвыпускать изделия двух видов (например, мотоциклы и велосипеды). В силуограниченности возможностей сборочного цеха в нем могут собирать за день либо25 мотоциклов (если не собирать вообще велосипеды), либо 100 велосипедов (еслине собирать вообще мотоциклы), либо какую-нибудь комбинацию тех и других,определяемую приемлемыми трудозатратами. Склад может принять не более 70изделий любого вида в сутки. Известно, что мотоцикл стоит в 2 раза дорожевелосипеда. Требуется найти такой план выпуска продукции, который обеспечил быпредприятию наибольшую выручку.
Такого рода задачи возникают повседневно в огромномколичестве, но в реальности число изделий гораздо больше двух, да идополнительных условий тоже больше. Решить подобную задачу путем перебора всехмыслимых вариантов часто невозможно даже на ЭВМ. В нашем примере, однако, в ЭВМнет необходимости — задача решается очень легко.
/> <td/> />Обозначим число выпускаемых за день мотоциклов х, велосипедов — у. Пусть т1 — время (в часах), уходящее на производство одного мотоцикла, а т2 — одного велосипеда. Из условия задачи следует, что т1 = 4т2.Если завод работает круглосуточно, то, очевидно, при одновременном выпускеобоих изделий
/>
или
/>
Но – 24/т2 — число максимальнопроизводимых велосипедов, равное 100. Итак, возможности производстваопределяют условие
/>
/> <td/> />Еще одно условие — ограниченная емкость склада:
Обозначим цену мотоцикла а1 (руб.), ценувелосипеда — а2 (руб.). По условию a1= 2а2. Общая цена дневной продукции
/>
Поскольку а2 — заданная положительная константа, то наибольшегозначения следует добиваться от величины
Итак, учитывая все условия задачи, приходим к еематематической модели: среди неотрицательных целочисленных решений системылинейных неравенств
/>
(7.71)
найти такое, которое соответствует максимуму линейнойфункции
f = 2х +у. (7.72)
Проще всего решить эту задачу чисто геометрически.Построим на плоскости (х, у) область, соответствующую неравенствам (7.71) иусловию неотрицательности х и у. Эта область выделена на рис.1 жирной линией.Всякая ее точка удовлетворяет неравенствам (7.71) и неотрицательностипеременных. Пунктирные линии на рисунке — семейство прямых, удовлетворяющихуравнению f = 2х + у = с (с разными значениями константы с).Вполне очевидно, что наибольшему возможному значению f, совместному спредыдущими условиями, соответствует жирная пунктирная линия, соприкасающаясяс областью М в точке Р.
/>
/>25
О 10 20 30 40 50 60 70 80
Рис. 1. Графическое решение задачи об оптимальномплане производства (к примеру 1)
Этой линии соответствует значение f= 80. Пунктирная линия правее хоть и соответствуетбольшему значениюf, но не имеет общихточек с М, левее — меньшим значениям f. Координатыточки Р (10, 60) — искомый оптимальный план производства.
Отметим, что нам «повезло» — решение (х, у) оказалосьцелочисленным. Если бы прямые
/>
пересеклись в точке с нецелочисленными координатами,мы бы столкнулись со значительными проблемами. Еще больше их было бы, если бынаш завод выпускал три и более видов продукции.
Прежде чем обсуждать возникающие при этомматематические проблемы, дадим формулировки нескольких классических задачлинейного программирования в общем виде.
Пример 2. Транспортная задача. Некий продукт(например, сталь) вырабатывается на m заводах Р1,Р2, ..., Рm, причем ежемесячная выработка составляет a1, а2, …, аmтонн, соответственно. Пусть эту сталь надо доставить на предприятия Q1, Q2, ..., Qk (всего k), причем b1, b2, ..., bk — ежемесячная потребность этих предприятий.Наконец, пусть задана стоимость cij<sub/> перевозки одной тонны стали с завода Pi на предприятие QJ.Естественно считать, что общее производство стали равно суммарной потребностив ней:
a1 + a2+ … + am = b1 + b2 + … + bk (7.73)
Необходимо составить план перевозок, при котором
1) была бы точно удовлетворена потребность в сталипредприятий Q1, Q2,...,Qk;
2) была бы вывезена вся сталь с заводов PI, Р2, ..., Рт;
3) общая стоимость перевозок была бы наименьшей.
Обозначим через Хij количество стали (в тоннах), предназначенной котправке с завода Рi на предприятие QJ.План перевозок состоит из (m×k)неотрицательных чисел xij<sub/>(i = 1, 2, ..., m; j = 1, 2, ..., k).
Таблица7.10Схемаперевозок сталиВ />
В />
В />
¼В />
ОтправленоИз />
/>
/>
/>
…/>
/>
Из />
/>
/>
/>
…/>
/>
… … … … … … …Из />
/>
/>
xm3
…/>
/>
Привезено/>
/>
/>
…/>
Первое условие примет вид
/>
(7.74)
Второе условие примет вид
/>
(7.75)
Раз стоимость перевозки одной тонны из Рi, в QJ равна сij, то общая стоимость S всехперевозок равна
/>
(7.76)
Таким образом, мы приходим к следующей чистоматематической задаче: дана система m+kлинейных алгебраических уравнений (7.74) и (7.75) с m·k неизвестными (обычно m·k » m+k) илинейная функция S. Требуется среди всех неотрицательныхрешений данной системы найти такое, при котором функция Sдостигает наименьшего значения (минимизируется).
Практическое значение этой задачи огромно, ее умелоерешение в масштабах нашей страны могло бы экономить ежегодно огромные средства.
Пример 3. Задача о диете. Пусть уврача-диетолога имеется n различных продуктов F1, F2, ..., Fn, из которых надо составить диету с учетом ихпитательности. Пусть для нормального питания человеку необходимо m
веществ N1, N2, …, Nm.Предположим, что за месяц каждому человеку необходимо g1 кг вещества N1,g2 кг вещества N2, ..., gm кг вещества Nm.Для составления диеты необходимо знать содержание питательных веществ в каждомпродукте. Обозначим через aij количество i-го питательного вещества, содержащегося в одном килограмме j-го продукта. Всю эту информацию представляют в виде, такназываемой, матрицы питательности (табл. 7.11).
Таблица 7.11МатрицапитательностиПитательное вещество Продукт/>
/>
…/>
/>
/>
/>
…/>
/>
/>
/>
…/>
… … … … …/>
/>
/>
…/>
Предположим, что диетолог уже выбрал диету, т.е. определил, что человекдолжен за месяц потреблять h1кг продукта F1,...,hn кг продукта Fn. Полное количество питательного вещества N1 будет
/>
По условию требуется, чтобы его, по крайней мере,хватило
/>
(7.77)
Точно то же и для остальных веществ. В целом
(I = 1, 2, …, m).
/> (7.78)
Эти условия определяют наличие минимума необходимыхпитательных веществ. Диета, для которой выполнены условия (7.78) — допустимаядиета. Предположим, что из всех допустимых диет должна быть выбрана самаядешевая. Пусть pi — цена 1 кг продукта Fi. Полная стоимостьдиеты, очевидно,
/>
(7.79)
Таким образом, мы пришли к задаче: найтинеотрицательное решение h1,..., hnсистемы неравенств (7.78), минимизирующее выражение (7.79).
В примерах, приведенных выше, имеется нечто общее.Каждый из них требует нахождения наиболее выгодного варианта в определеннойэкономической ситуации. С чисто математической стороны в каждой задачетребуется найти значение нескольких неизвестных так, чтобы
1) все эти значения были неотрицательны;
2) удовлетворяли системе линейных уравнений илилинейных неравенств;
3) при этих значениях некоторая линейная функция имела бы минимум (илимаксимум). Таким образом, линейное программирование — это математическаядисциплина, изучающая методы нахождения экстремального значения линейнойфункции нескольких переменных при условии, что последние удовлетворяютконечному числу линейных уравнений и неравенств. Запишем это с помощью формул:дана система линейных уравнений и неравенств.
Запишем это с помощью формул: дана система линейныхуравнений и неравенств
/>
(7.80)
и линейная функция
/>
(7.81)
Требуется найти такое неотрицательное решение
/> (7.82)
системы (7.80), чтобы функция/принимала наименьшее(или наибольшее) значение.
Условия (7.80) называют ограничениями данной задачи,а функцию f — целевой функцией (или линейной формой). В приведенных вышепримерах ограничения имели вид не уравнений, а неравенств. Заметим, чтоограничения в виде неравенств, всегда можно свести ксистеме в виде равенств (способом введения добавочных неизвестных).
Так, для неравенства
/> (7.83)
вводя добавочное неизвестное хn+1,получаем
/>
(7.84)
Потребовав его неотрицательности наряду с остальныминеизвестными, получим, что условие хn+1³ 0 превращает (7.84) в (7.83). Введя по отдельномудополнительному неизвестному для каждого из неравенств, получим системууравнений, равносильную исходной системе неравенств.
Пример. Дана система неравенств
/>
Сведем ее к системе уравнений. Получим
/>
После оптимизации значениями дополнительныхнеизвестных следует пренебречь.
СИМПЛЕКС-МЕТОД
Для решения ряда задач линейного программированиясуществуют специальные методы. Есть, однако, общий метод решения всех такихзадач. Он носит название симплекс-метода и состоит из алгоритма отысканиякакого-нибудь произвольного допустимого решения и алгоритма последовательногоперехода от этого решения к новому допустимому решению, для которого функция fизменяется в нужном направлении (для получения оптимального решения).
Пусть система ограничений состоит лишь из уравнений
/>
(7.85)
и требуется отыскать минимум линейной функции (7.81).Для отыскания произвольного опорного решения приведем (7.85) к виду, в которомнекоторые r неизвестных выражены через остальные, асвободные члены неотрицательны (как это сделать — обсудим позднее):
/>
(7.86)
Неизвестные х1, х2, ..., хr — базисные неизвестные, набор {х1, х2, ..., хr}называется базисом, а остальные неизвестные {xr+1,хr+2, …, хn}- свободные. Подставляя (7.86) в (7.81), выразим функцию f черезсвободные неизвестные:
/>
(7.87)
Положим все свободные неизвестные равными нулю:
/> (7.88)
Найдем из системы (7.86) значения базисныхнеизвестных
/> (7.89)
Полученное таким образом допустимое решение
/>
отвечает базису x1,x2, ..., хr,т.е. является базисным решением. Допустим для определенности, что мы ищем минимумf. Теперь нужно отданного базиса перейти кдругому с таким расчетом, чтобы значение линейной функции fпри этом уменьшилось. Проследим идею симплекс-метода на примере.
Пример 1. Дана система ограничений
/>
Требуется минимизировать линейную функцию f =х2 – х3. В качестве свободных переменных выберем х2и x3. Тогда данная система ограниченийпреобразуется к виду
/>
Таким образом, базисное решение (3, О, О, 1). Так каклинейная функция уже записана в свободных неизвестных, то ее значение для данногобазисного решения f = 0. Для уменьшения этого значения можно уменьшить х2или увеличить х3. Но х2 в данном базисе равно нулю ипотому его уменьшать нельзя. Попробуем увеличить x3. Первое изуравнений имеет ограничение х3 = 1 (из условия х1³ 0), второе — не дает ограничений.Далее, берем х3= 1, х2 не меняем и получаем новоедопустимое решение (О, О, 1, 3), для которого f= -1- уменьшилось. Найдем базис, которому соответствует это решение (он состоит,очевидно, из переменных x3, х4).От предыдущей системы ограничений переходим к новой:
/>
а форма в новых свободных переменных имеет вид
/>
Теперь попробуем повторить предыдущую процедуру. Дляуменьшения f надо уменьшить либо x1, либох2, но это невозможно, так как в этом базисе
x1 = О, х2= 0.
Таким образом, данное базисное решение являетсяоптимальным, и min f= -1 при x1= О, х2 = 0, хз = 1, x4 = 3.
Приведем алгоритм симплекс-метода в общем виде.Обычно все вычисления по симплекс-методу сводят в стандартные таблицы.
Запишем систему ограничений в виде
/>
(7.90)
а функцию f
/> (7.91)
Тогда очередной шаг симплекс-процесса будет состоятьв переходе от старого базиса к новому таким образом, чтобы значение линейнойфункции, по крайней мере, не увеличивалось.
Данные о коэффициентах уравнений и линейной функциизанесем в табл. 7.12.
Таблица 7.12
Симплекс-таблица
Базис Св.чл.
/>
…/>
…/>
/>
…/>
…/>
/>
/>
1 … …/>
…/>
…/>
… … … … … … … … … … … …/>
/>
… 1 …/>
…/>
…/>
… … … … … … … … … … … …/>
/>
… … 1/>
…/>
…/>
/>
/>
… …/>
…/>
…/>
Сформулируем алгоритм симплекс-метода применительно кданным, внесенным в табл. 7.12.
1. Выяснить, имеются ли в последней строке таблицыположительные числа (γ0не принимается во внимание). Если всечисла отрицательны, то процесс закончен; базисное решение (b1,b2, ..., br, 0, ..., 0) являетсяоптимальным; соответствующее значение целевой функции f= γ0. Если в последней строке имеются положительные числа,перейти к п. 2.
2. Просмотреть столбец, соответствующийположительному числу из последней строки, и выяснить, имеются ли в немположительные числа. Если ни в одном из таких столбцов положительных чисел нет,то оптимального решения не существует. Если найден столбец, содержащий хотя быодин положительный элемент (если таких столбцов несколько, взять любой из них),пометить этот столбец и перейти к п. 3.
3. Разделить свободные члены на соответствующиеположительные числа из выделенного столбца и выбрать наименьшее частное.Отметить строку таблицы, соответствующую наименьшему частному. Выделить разрешающий элемент, стоящий на пересечении отмеченных строки и столбца.Перейти к п. 4.
4. Разделить элементы выделенной строки исходнойтаблицы на разрешающий элемент (на месте разрешающего элемента появитсяединица). Полученная таким образом новая строка пишется на месте прежней вновой таблице. Перейти к п. 5.
5. Каждая следующая строка новой таблицы образуетсясложением соответствующей строки исходной таблицы и строки, записанной в п. 4,которая предварительно умножается на такое число, чтобы в клетках выделенногостолбца при сложении появились нули. На этом процесс заполнения новой таблицызаканчивается, и происходит переход к п. 1.
Таким образом, используя алгоритм симплекс-методаприменительно к симплекс-таблице, мы можем найти оптимальное решение илипоказать, что его не существует. Результативность комплекс-метода гарантируетсяследующей теоремой (приведем ее без доказательства):если существуетоптимальное решение задачи линейного программирования, то существует и базисноеоптимальное решение. Это решение может быть получено через конечное число шаговсимплекс-методом, причем начинать можно с любого исходного базиса.
Ранее мы предполагали, что если система ограниченийзадана в виде (7.85), то перед первым шагом она уже приведена к виду(7.86), гдеbi≥0 (I=1,2,…, r). Последнее условие необходимо для использованиясимплекс-метода. Рассмотрим вопрос об отыскании начального базиса.
Один из методов его получения – метод симплексногопреобразования.
Прежде всего проверяем, есть ли среди свободныхчленов отрицательные. Если свободные члены не являются числаминеотрицательными, то добиться их неотрицательности можно несколькими способами:
1) умножить уравнения, содержащие отрицательные свободные члены, на –1;
2) найти среди уравнений, содержащих отрицательные свободные члены,уравнение с максимальным по абсолютной величине отрицательным свободным членоми затем сложить это уравнение со всеми остальными, содержащими отрицательныесвободные члены, предварительно умножив его на –1.
Затем, используя действия, аналогичные указанным впп. 3-5 алгоритма симплекс-метода, совершаем преобразования исходной таблицы дотех пор, пока не получим неотрицательное базисное решение.
Пример 2. Найти исходное неотрицательноебазисное решение системы ограничений.
/>
Так как условие неотрицательности свободных членовсоблюдается, приступим к преобразованиям исходной системы, записывая результатыв таблицу. Согласно алгоритму просматриваем первый столбец. В этом столбцеимеется единственный положительный элемент а31. Делим на 8,654 всекоэффициенты и свободный член третьей строки, после чего умножаем каждыйкоэффициент на 8,704 и складываем с соответствующими коэффициентами второйстроки. Первая строка преобразований не требует, так как коэффициент принеизвестном x1 равен нулю. В результатеполучаем
0,00000 -5,87100 6,54300 -9,99600 7,61800 0,86400
0,00000 0,68512 17,46384 8,57990 -3,19062 9,79929
1,00000 -0,77756 0,97677 0,89808 0,62769 1,11584
Продолжая просматривать второй столбец и совершаяаналогичные преобразования, имеем
0,00000 0,00000 156,19554 63,52761 -19,72328 84,83688
0,00000 1,00000 25,49013 12,52318 -4,65701 14,30299
1,00000 0,00000 20,79687 10,63560 -2,99341 12,24727
И, наконец, на третьем шаге находим исходный базис.Его образуют неизвестные x1, х2,х3. Неизвестные х4, х5 являются свободными:
0,00000 0,00000 1,00000 0,40672 -0,12627 0,54315
0,00000 1,00000 0,00000 2,15588 -1,43829 0,45815
1,00000 0,00000 0,00000 2,17713 -0,36733 0,95155
Контрольные вопросы и задания1. Приведите примеры задач, приводящих к общейпостановке задачи линейного программирования.
2. Сформулируйте задачу линейного программирования.
3. Сколько решений может иметь задача линейногопрограммирования?
4. По каким причинам может отсутствовать решениезадачи линейного программирования?
5. Каким образом неравенства из системы ограниченийможно заменить уравнениями? Как задачу отыскания максимума линейной формысвести к задаче отыскания минимума?
6. Необходимо ли учитывать при записи решениядополнительные неизвестные, вводимые при переходе от неравенств к уравнениям?
7. Как найти начальный базис?
8. Сформулируйте алгоритм симплекс-метода.
9. Сформулируйте теорему о конечности алгоритмасимплекс-метода.
10. Найдите максимум функции z= 4xl + 3х2 (xi<sub/>≥ 0) при условии
x1-x2≥ -2,
5x1+3x2≤15,
x2≤2,5,
2x1-x2≥ -2,
x1-2x2≤ 2.
11. Для откорма крупного рогатого скота используетсядва вида кормов b1и b2, в которыевходят питательные вещества а1, а2, а3 и a4.Содержание количеств единиц питательных веществ в одном килограмме каждого корма, стоимость одного килограмма корма и норма содержания питательныхвеществ в дневном рационе животного представлены в таблице. Составьте рационпри условии минимальной стоимости.
Питательные вещества Вид кормов Норма содержания питательного вещества />B1
B2
/>A1
3 4 24A2
1 2 18A3
4 20A4
1 6 Стоимость 1 кг корма, руб. 2 1 />12. Трикотажная фабрика использует для производствасвитеров и кофточек чистую шерсть, силон и нитрон, запасы которых составляют,соответственно, 800, 400 и 300 кг.
Вид сырья в пряже Затраты пряжи на 10 шт., Свитер Кофточка Шерсть 4 2 Силон 2 I Нитрон 1 1 Прибыль, руб. 6 5Количество пряжи (кг), необходимое для изготовления10 изделий, а также прибыль, получаемая от их реализации, приведены в таблице.Составьте план производства изделий, обеспечивающий получение максимальнойприбыли.
13. При подкормке посевов необходимо внести на 1 гапочвы не менее 8 единиц химического вещества А, не менее 21 единиц химическоговещества В и не менее 16 единиц химического вещества С. Фермер закупаеткомбинированные удобрения двух видов I и П. В таблицеуказано содержание количества единиц химического вещества в 1 кг каждого видаудобрений и цена 1 кг удобрений. Определите потребность фермера в удобрениях I и II вида на 1 га посевной площадипри минимальных затратах на их приобретение.
Химические вещества Содержание химических веществ в I кг удобрения I II А 1 5 В 12 3 С 4 4 Цена 1 кг удобрения, руб 5 2
Заключение.
Прирешении задачи линейного программирования целесообразно использованиекомпьютера. В этом случае можно составить программу, решающую задачу. Учитывая,что программирование довольно трудоемко, можно посоветовать воспользоваться дляоформления результатов расчетов табличным процессором. Кроме того, еслиполучившаяся модель задачи слишком громоздка, можно воспользоватьсяматематическими пакетами, которые позволяют получить решение задачи линейногопрограммирования. И, наконец, еще один возможный вариант применения компьютеров- комбинирование всех вышеуказанных способов.
Литература:
А.В.Могилев, Н.И.Пак, Е.К.Хеннер, Информатика,
М., Академия, 2003.-816 с.