- 24 -

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Шадринский Государственный Педагогический институт

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

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

Курсовая работа.

Выполнили:

Студентки 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, совместному с предыдущими условиями, соответствует жирная пунк­тирная линия, соприкасающаяся с областью М в точке Р.

2 5

О 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.10

Схема перевозок стали

	В	В	В		В	Отправлено
Из				…
Из				…
…	…	…	…	…	…	…
Из			xm3	…
Привезено				…

Первое условие примет вид

(7.74)

Второе условие примет вид

(7.75)

Раз стоимость перевозки одной тонны из Р_i, в Q_J равна с_ij, то общая стоимость S всех перевозок равна

(7.76)

Таким образом, мы приходим к следующей чисто математической задаче: дана система m+k линейных алгебраических уравнений (7.74) и (7.75) с m·k неизвестны­ми (обычно m·k » m+k) и линейная функция S. Требуется среди всех неотрица­тельных решений данной системы найти такое, при котором функция S достигает наименьшего значения (минимизируется).

Практическое значение этой задачи огромно, ее умелое решение в масштабах нашей страны могло бы экономить ежегодно огромные средства.

Пример 3. Задача о диете. Пусть у врача-диетолога имеется n различных продук­тов F₁, F₂, ..., F_n, из которых надо составить диету с учетом их питательности. Пусть для нормального питания человеку необходимо m

веществ N₁, N₂, …, N_m. Предположим, что за месяц каждому человеку необходимо ₁ кг вещества N₁, ₂ кг вещества N₂, ..., _m кг вещества N_m. Для составления диеты необходимо знать содержание питательных веществ в каждом продукте. Обозначим через a_ij количе­ство i-го питательного вещества, содержащегося в одном килограмме j-го продукта. Всю эту информацию представляют в виде, так называемой, матрицы питательно­сти (табл. 7.11).

Таблица 7.11

Матрица питательности

Питательное вещество	Продукт
			…
			…
			…
…	…	…	…	…
			…

Предположим, что диетолог уже выбрал диету, т.е. определил, что человек дол­жен за месяц потреблять ₁ кг продукта F₁,...,_n кг продукта F_n. Полное количество питательного вещества N₁ будет