МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИШадринский Государственный Педагогический институт

КОМПЬЮТЕРНОЕ МАТЕМАТИЧЕСКОЕ

МОДЕЛИРОВАНИЕ В ЭКОНОМИКЕ.

Курсовая работа.
Выполнили:

Студентки 201 гр.

Благодарева Юлия  Григорьевна

Реутова Елена Александровна

Руководитель:

Пайвина Юлия Васильевна
Шадринск, 2003 г.

Оглавление

Введение…………………………………………………….….……..3

1.                 Постановка задачи линейного программирования….…...4

2.                 Симплекс-метод……………………………………………14

3.                 Контрольные вопросы и задания…………………………21

Заключение……………………………………………….…………..24

    Литература…………………………………………………….………25

Введение

В последние годы мы особенно отчетливо ощутили, что нет ничего важнее для общества, чем здоровая экономика. Научное исследование основ функционирования экономики – сложная и интересная деятельность. Математические методы в ней играют возрастающую с каждым десятилетием роль, а реализация возникающих  при этом математических моделей и получение практически важных результатов невозможны без ЭВМ.
ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

В данном параграфе рассматривается лишь один из разделов - оптимальное пла­нирование - и внутри него одна из моделей, так называемое, линейное программи­рование. Это связано с относительной простотой и ясностью как содержательной постановки соответствующих задач, так и методов решения. О таких интересных, но более сложных проблемах, как выпуклое программирование, динамическое программирование, теория игр мы лишь упомянем, отсылая читателей за подроб­ностями к специальной литературе. Отметим еще, что термин «программирование» в названии этих разделов теории оптимального планирования весьма условен, связан с историческими обстоятельствами и к программированию в общепринятом сейчас смысле прямого отношения не имеет.

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

Пример 1. На некотором предприятии могут выпускать изделия двух видов (например, мотоциклы и велосипеды). В силу ограниченности возможностей сборочного цеха в нем могут собирать за день либо 25 мотоциклов (если не собирать вообще велосипеды), либо 100 велосипедов (если не собирать вообще мотоциклы), либо какую-нибудь комбинацию тех и других, определяемую прием­лемыми трудозатратами. Склад может принять не более 70 изделий любого вида в сутки. Известно, что мотоцикл стоит в 2 раза дороже велосипеда. Требуется найти такой план выпуска продукции, который обеспечил бы предприятию наиболь­шую выручку.

Такого рода задачи возникают повседневно в огромном количестве, но в реаль­ности число изделий гораздо больше двух, да и дополнительных условий тоже больше. Решить подобную задачу путем перебора всех мыслимых вариантов часто невозможно даже на ЭВМ. В нашем примере, однако, в ЭВМ нет необходимости - задача решается очень легко.


Обозначим число выпускаемых за день мотоциклов х, велосипедов - у. Пусть т₁ - время (в часах), уходящее на производство одного мотоцикла, а т₂ - одного велоси­педа. Из условия задачи следует, что т₁ = 4т₂. Если завод работает круглосуточно, то, очевидно, при одновременном выпуске обоих изделий




или




Но – 24/т₂ - число максимально производимых велосипедов, равное 100. Итак, воз­можности производства определяют условие


Еще одно условие - ограниченная емкость склада:
Обозначим цену мотоцикла а₁ (руб.), цену велосипеда - а₂ (руб.). По условию a₁ = 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 заводах Р₁, Р₂, ..., Р_m, причем ежемесячная выработка составляет a₁,  а₂, …, а_m тонн, соответственно. Пусть эту сталь надо доставить на предприятия Q₁, Q₂, ..., Q_k (всего k), причем b₁, b₂, ..., b_k - ежемесячная потребность этих предприятий. Наконец, пусть задана стоимость c_ij  перевозки одной тонны стали с завода P_i на предприятие Q_J. Естественно считать, что общее производство стали равно суммар­ной потребности в ней:

a₁ + a₂ + … + a_m = b₁ + b₂ + … + b_k                                            (7.73)
Необходимо составить план перевозок, при котором

1) была бы точно удовлетворена потребность в стали предприятий Q₁, Q₂,..., Q_k;

2) была бы вывезена вся сталь с заводов P_I, Р₂, ..., Р_т;

3) общая стоимость перевозок была бы наименьшей.

Обозначим через Х_ij количество стали (в тоннах), предназначенной к отправке с завода Р_i на предприятие Q_J. План перевозок состоит из (m×k) неотрицательных чисел x_ij (i = 1, 2, ..., m; j = 1, 2, ..., k).

Таблица 7.12

                                        

Симплекс-таблица





Сформулируем алгоритм симплекс-метода применительно к данным, внесенным в табл. 7.12.

1. Выяснить, имеются ли в последней строке таблицы положительные числа (γ₀ не принимается во внимание). Если все числа отрицательны, то процесс закончен; базисное решение (b₁, b₂, ..., b_r, 0, ..., 0) является оптимальным; соответствующее значение целевой функции f = γ₀. Если в последней строке имеются положительные числа, перейти к п. 2.

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

3. Разделить свободные члены на соответствующие положительные числа из вы­деленного столбца и выбрать наименьшее частное. Отметить строку таблицы, соответствующую   наименьшему   частному.   Выделить   разрешающий   элемент, стоящий на пересечении отмеченных строки и столбца. Перейти к п. 4.

4. Разделить элементы выделенной строки исходной таблицы на разрешающий элемент (на месте разрешающего элемента появится единица). Полученная таким образом новая строка пишется на месте прежней в новой таблице. Перейти к п. 5.

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

 Таким образом, используя алгоритм симплекс-метода применительно к симплекс-таблице, мы можем найти оптимальное решение или показать, что его не существует. Результативность комплекс-метода гарантируется следующей теоремой (приведем ее без доказательства): если существует оптимальное решение задачи линейного программирования, то существует и базисное оптимальное решение. Это решение может быть получено через конечное число шагов симплекс-методом, причем начинать можно с любого исходного базиса. 

 Ранее мы предполагали, что если система ограничений задана в виде (7.85), то перед первым шагом она уже приведена к виду(7.86), где b_i≥0 (I=1,2, …, r). Последнее условие необходимо для использования симплекс-метода. Рассмотрим вопрос об отыскании начального базиса.

 Один из методов его получения – метод симплексного преобразования.

 Прежде всего проверяем, есть ли среди свободных членов отрицательные. Если свободные члены не являются числами неотрицательными, то добиться их неотрицательности можно несколькими способами:

1)                        умножить уравнения, содержащие отрицательные свободные члены, на –1;

2)                        найти среди уравнений, содержащих отрицательные свободные члены, уравнение с максимальным по абсолютной величине отрицательным свободным членом и затем сложить это уравнение со всеми остальными, содержащими отрицательные свободные члены, предварительно умножив его на –1.

 Затем, используя действия, аналогичные указанным в пп. 3-5 алгоритма симплекс-метода, совершаем преобразования исходной таблицы до тех пор, пока не получим неотрицательное базисное решение.

Пример 2. Найти исходное неотрицательное базисное решение системы ограничений.





Так как условие неотрицательности свободных членов соблюдается, приступим к преобразованиям исходной системы, записывая результаты в таблицу. Согласно алгоритму просматриваем первый столбец. В этом столбце имеется единственный положительный элемент а₃₁. Делим на 8,654 все коэффициенты и свободный член третьей строки, после чего умножаем каждый коэффициент на 8,704 и складываем с соответствующими коэффициентами второй строки. Первая строка преобразований не требует, так как коэффициент при неизвестном x₁ равен нулю. В результате получаем

   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

И, наконец, на третьем шаге находим исходный базис. Его образуют неизвест­ные x₁, х₂, х₃. Неизвестные х₄, х₅ являются свободными:

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 = 4x_l + 3х₂ (x_i ≥ 0) при условии

                                   

x₁-x₂≥ -2,

5x₁+3x₂≤15,

x₂≤ 2,5,

2x₁-x₂≥ -2,

x₁-2x₂≤ 2.

11. Для откорма крупного рогатого скота используется два вида кормов b₁и b₂, в которые входят питательные вещества а₁, а₂, а₃ и a₄. Содержание количеств единиц питательных веществ  в  одном  килограмме каждого  корма,  стоимость одного килограмма корма и норма содержания питательных веществ в дневном рационе животного представлены в таблице. Составьте рацион при условии мини­мальной стоимости.





12. Трикотажная фабрика использует для производства свитеров и кофточек чистую шерсть, силон и нитрон, запасы которых составляют, соответственно, 800, 400 и 300 кг.



Количество пряжи (кг), необходимое для изготовления 10 изделий, а также прибыль, получаемая от их реализации, приведены в таблице. Составьте план производства изделий, обеспечивающий получение максимальной прибыли.

13. При подкормке посевов необходимо внести на 1 га почвы не менее 8 единиц химического вещества А, не менее 21 единиц химического вещества В и не менее 16 единиц химического вещества С. Фермер закупает комбинированные удобрения двух видов I и П. В таблице указано содержание количества единиц химического вещества в 1 кг каждого вида удобрений и цена 1 кг удобрений. Определите потреб­ность фермера в удобрениях I и II вида на 1 га посевной площади при минимальных затратах на их приобретение.


       
Заключение.

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


Литература
:
А.В.Могилев, Н.И.Пак, Е.К.Хеннер, Информатика,

М., Академия, 2003.-816 с.