3946
.pdfМинистерство образования и науки Российской Федерации Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Хабаровская государственная академия экономики и права»
Кафедра математики и математических методов в экономике
Математика
Экономико-математические методы
Методические указания и контрольные задания для студентов 2, 3, 4-го курсов заочной формы обучения
всех специальностей
Хабаровск 2007
2
ББК В 1 Х 12
Математика. Экономико-математические методы : метод. указания и контрольные задания для студентов 2, 3, 4-го курсов заочной формы обучения всех специальностей / сост. П. Я. Бушин, В. Н.Захарова. – Хабаровск : РИЦ ХГАЭП, 2007. – 24 с.
Рецензент канд. физ.-мат. наук, доцент кафедры высшей математики ТОГУ В. М. Манаков.
Утверждено издательско-библиотечным советом академии в качестве методических указаний для студентов
Бушин Павел Яковлевич
Захарова Валентина Никитична
Математика. Экономико-математические методы Методические указания и контрольные задания
для студентов 2, 3, 4-го курсов заочной формы обучения всех специальностей
Редактор Г.С. Одинцова
Подписано в печать |
Формат 60 х 84/16 . Бумага писчая. |
|
Печать офсетная. Усл.п.л. 1,4. |
Уч.-изд.л. 1,0. |
Тираж 150 экз. |
Заказ № |
|
|
___________________________________________________________
680042, Хабаровск, ул. Тихоокеанская, 134, ХГАЭП, РИЦ
© Хабаровская государственная академия экономики и права, 2007
3
Содержание
Предисловие…………………………………………………………………….4
Основные вопросы курса…………………………………………………........4
1.Симплексный метод в линейном программировании…………..5
2.Двойственность в линейном программировании………………12
3.Транспортная задача……………………………………………..14
4.Сетевое планирование и управление. Расчёт
основных показателей……………………………………………18
Библиографический список…………………………………………………..24
4
Предисловие
Данные указания содержат основные вопросы курса, методические указания и контрольные задания для выполнения работ по курсу «Экономико-математические методы».
В методических указаниях приведены необходимые сведения из отдельных разделов курса. Решены типовые задачи.
Методические указания составлены для студентов-заочников. Перед тем как приступить к решению контрольной работы, необходимо разобрать теоретические вопросы по соответствующему разделу и решения типовых задач.
Основные вопросы курса
1.Система m линейных уравнений с n неизвестными; базисные и свободные неизвестные; понятие базисного решения. Система с базисом. Метод Жордана – Гаусса . Каноническая система. Опорное решение. Метод однократного замещения в канонической системе.
2.Примеры экономико-математических моделей (задачи: использование сырья, о диете, транспортная). Задача линейного программирования (стандартная, основная, общая). Преобразование системы ограничений.
3.Общая теория линейного программирования. Понятие о выпуклых множествах. Множество допустимых решений систем линейных уравнений и неравенств. Экстремум целевой функции.
4.Каноническая задача линейного программирования. Симплексные таблицы. Симплексный метод. Альтернативный оптимум. Графический метод.
5.Двойственность в линейном программировании. Двойственная задача к стандартной и основной. Основная теорема двойственности. Теорема равновесия. Экономическая интерпретация двойственных переменных.
6.Транспортная задача. Разрешимость транспортной задачи. Методы построения исходного допустимого плана. Метод потенциалов.
7.Понятие о нелинейном программировании. Понятие о целочисленном программировании. Простейшие задачи динамического программирования.
8.Сетевое планирование и управление. Сетевые графики, основные показатели. Метод критического пути.
5
Методические указания к отдельным темам программы
1. Симплексный метод в линейном программировании
Рассмотрим математическую модель стандартной задачи линейного программирования (система ограничений содержит знаки неравенств).
Z c1x1 |
c2 x2 |
... |
cn xn |
max |
|
||
a11 x1 |
a12 x2 |
... |
a1n xn |
b1, |
|
||
a21 x1 |
a22 x2 |
... |
a2n xn |
b2 , |
(1) |
||
|
|
|
|
|
|
|
|
am1x1 |
am2 x2 |
... |
amn xn |
bm . |
|
||
|
|
|
|
|
|
|
|
|
x j |
0; |
j 1, n. |
|
|
Предположим, что все свободные члены bi системы неотрицательны. Приведём систему к основной, добавив в левые части неотрицательные балансовые переменные Xn+1, …,Xn+m.
Z c1x1 |
c2 x2 |
... |
cn xn |
max |
|
|
|
|
||
a11 x1 |
a12 x2 |
... |
a1n xn |
xn 1 |
|
b1, |
|
|
||
a21 x1 |
a22 x2 |
... |
a2n xn |
|
xn |
2 |
b2 |
, |
(2) |
|
|
|
|
|
|
|
|
|
|
|
|
am1x1 |
am2 x2 |
... |
amn xn |
|
xn |
m |
bm . |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
x j |
0; |
j 1, n |
m. |
|
|
|
|
Система ограничений в задаче (2) является канонической, т.к. она является системой с базисом и все её свободные члены неотрицательны. Такой системе соответствует опорное решение (базисное неотрицательное) x0 =(0, 0, …,0, b1, b2, …, bm), в котором все свободные неизвестные x1, x2,
…, xn равны нулю, а базисные xn+1, xn+2,…, xn+m равны соответствующим
свободным членам b1, b2, …, bm. |
|
|
|
|
|
|
|
|||||
|
Симплексный метод – это метод последовательного |
улучшения |
||||||||||
опорного решения. Задача решается в симплексных таблицах. |
|
|
||||||||||
|
|
|
0 |
С1 |
С2 |
|
Сn |
0 |
0 |
|
0 |
|
Ci |
|
Баз |
bi |
x1 |
x2 |
… |
xn |
xn+1 |
xn+2 |
… |
xn+m |
Ө |
0 |
|
xn+1 |
b1 |
a11 |
a12 |
… |
a1n |
1 |
0 |
… |
0 |
|
0 |
|
xn+2 |
b2 |
a21 |
a22 |
… |
a2n |
0 |
1 |
… |
0 |
|
- |
|
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
0 |
|
xn+m |
bm |
am1 |
am2 |
… |
amn |
0 |
0 |
… |
1 |
|
|
|
Z |
0 |
-C1 |
-C2 |
|
-Cn |
0 |
0 |
|
0 |
|
Этой таблице соответствует опорное решение Х0=(0, 0, …,0, b1, b2, …, bm) и соответствующее ему значение целевой функции Z0=0.
Последняя строка таблицы называется оценочной и заполняется по формуле оценок
|
6 |
|
a0k |
ci aik ck . |
(3) |
|
i |
|
(Оценка при неизвестной xк равна сумме произведений элементов первого столбца на соответствующие элементы столбца xk минус Сk, стоящее над столбцом).
Условием оптимальности неотрицательность оценок
каноническая задача линейного ограничений каноническая, а свободные неизвестные.
Алгоритм симплексного метода
1.Приводим систему ограничений задачи к канонической и записываем в симплексную таблицу Элементы оценочной строки вычисляются по формуле оценок (3).
2.Если среди оценок симплексной таблицы при решении на максимум нет отрицательных оценок, то соответствующее опорное решение является оптимальным.
3.Если в оценочной строке содержится отрицательная оценка, а в столбце над ней нет положительных элементов, то целевая функция не ограничена сверху на множестве допустимых (неотрицательных) решений. Задача не имеет оптимального решения.
4.Если в каждом столбце с отрицательной оценкой имеется хотя бы один положительный элемент, то переходим к ''лучшему'' опорному решению. Для этого:
а) выбираем разрешающий столбец по наименьшей отрицательной оценке;
б) выбираем разрешающую строку. Для этого вычисляем Ө как отношение свободных членов к положительным элементам разрешающего столбца. Выделяем разрешающий элемент, соответствующий наименьшему Ө;
в) элементы разрешающей строки делим на разрешающий элемент, записываем единичные столбцы, соответствующие базисным неизвестным;
г)элементы остальных строк вычисляем по формуле прямоугольников
|
|
|
aik |
aik |
aqp aqk |
aip |
(4) |
|
|
|
|
aqp |
|
||
aik |
aip |
|
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
aqk |
|
aqp |
|
|
|
7
д) элементы оценочной строки также вычисляются по формуле «прямоугольников» и для контроля вычислений по формуле оценок.
Процесс вычислений продолжается до тех пор, пока не возникнут ситуации пунктов 1 или 2.
Решим пример, используя алгоритм.
Пример. На предприятии имеется три вида сырья и можно производить два вида продукции. Данные о расходе сырья на производство единицы продукции, запасов сырья и прибыли от реализации единицы продукции предоставлены в таблице
Вид сырья |
Запасы сырья |
Расход сырья на 1 ед. продукции |
|
|
|
А |
В |
1 |
45 |
3 |
4 |
2 |
31 |
5 |
2 |
3 |
30 |
2 |
3 |
Прибыль от реализации 1 ед. |
7 |
5 |
|
продукции |
|
|
Найти оптимальный план выпуска продукции, при котором предприятие получит наибольшую прибыль.
Решить задачу симплексным методом и графически.
Решение. Составим математическую модель. Обозначим через х1 и х2 выпуск продукции А и В соответственно. Затраты материала первого сорта на план х (х1, х2) составят 3х1 + 4х2, и они не должны превосходить запасов, т.е. 45 кг:
3х1 + 4х2 45.
Аналогичны ограничения по материалу второго сорта:
5х1 + 2х2 35
и по материалу третьего сорта
2х1 + 3х2 30.
Прибыль от реализации х1 единиц А и х2 – В составит z = 7x1 + 5x2 – целевая функция задачи.
Получили модель задачи:
3х1 |
+ 4х2 |
45, |
5х1 |
+ 2х2 |
31, |
2х1 |
+ 3х2 |
30. |
х1 0; x2 |
0 |
z = 7x1 + 5x2 |
max |
Вводом балансовых переменных х3, х4, х5 приводим модель к каноническому виду
3x1 |
+ 4x2 |
+ x3 |
= 45, |
5x1 |
+ 2x2 |
+ x4 |
= 31, |
2x1 |
+ 3x2 |
|
+ x5 = 30. |
8
|
|
|
|
xj |
0; (j=1,...,5); |
|
|
|
|
|
|
|
|
z = 7x1 + 5x2 |
max . |
|
|
|
|
Составим симплексную таблицу: |
|
|
|
|
|
||||
|
cj |
базис |
аi0 |
7 |
5 |
0 |
0 |
0 |
|
|
|
(xj) |
|
х1 |
х2 |
х3 |
х4 |
х5 |
|
|
0 |
x3 |
45 |
3 |
4 |
1 |
0 |
0 |
|
|
0 |
x4 |
31 |
5 |
2 |
0 |
1 |
0 |
|
|
0 |
x5 |
30 |
2 |
3 |
0 |
0 |
1 |
|
|
|
Z |
0 |
-7 |
-5 |
0 |
0 |
0 |
|
Первые три строки этой таблицы содержат в условной форме систему уравнений (ограничений) в канонической задаче, а именно: в столбцах ''ai0'' записываются в свободные члены уравнений, в столбцах ''х1'', ''х2'',..., ''х5'' – коэффициенты при соответствующих неизвестных этой системы.
Слева от столбца ''ai0'' в столбце ''xj'' выписываются базисные неизвестные, содержащиеся в соответствующих уравнениях системы.
Верхняя строка и крайний левый столбец содержат коэффициенты при соответствующих неизвестных в целевой функции z.
Последняя строка называется оценочной, а элементы строки – оценками. Первый элемент а00 оценочной строки представляет собой значение целевой функции z на начальном опорном плане:
х0 = (0, 0, 45, 31, 30).
Это значение может быть получено как результат скалярного умножения вектора-столбца ''сj'' на вектор-столбец свободных членов ''аi0'':
а00 = 0 45 0 31 0 30 0.
Оценки при неизвестных вычисляются по правилу: оценка при хj равна сумме произведений элементов первого столбца на соответствующие элементы столбца xj минус коэффициент сj, записанный над столбцом хj. Так оценка при х1 равна
|
|
|
а01 = 0 3 0 5 0 2 7 |
7 . |
|
|
|||||
Оценки при всех базисных неизвестных всегда равны нулю. |
|
||||||||||
Составим симплексную таблицу. |
|
|
|
|
|
|
|||||
cj |
базис |
аi0 |
|
7 |
|
5 |
0 |
|
0 |
0 |
|
|
(xj) |
|
|
х1 |
|
х2 |
х3 |
|
х4 |
х5 |
|
0 |
x3 |
45 |
|
3 |
|
4 |
1 |
|
0 |
0 |
15 |
0 |
x4 |
31 |
|
5 |
|
2 |
0 |
|
1 |
0 |
31/5 |
0 |
x5 |
30 |
|
2 |
|
3 |
0 |
|
0 |
1 |
15 |
|
z |
0 |
|
-7 |
|
-5 |
0 |
|
0 |
0 |
|
0 |
x3 |
132/5 |
|
0 |
|
14/5 |
1 |
|
-3/5 |
0 |
132/5 |
7 |
x1 |
31/5 |
|
1 |
|
2/5 |
0 |
|
1/5 |
0 |
31/2 |
0 |
x5 |
88/5 |
|
0 |
|
11/5 |
0 |
|
-2/5 |
1 |
88/11 |
9
|
z |
217/5 |
0 |
–11/5 |
0 |
7/5 |
0 |
|
0 |
x3 |
4 |
0 |
0 |
1 |
–1/11 |
–14/11 |
|
7 |
x1 |
3 |
1 |
0 |
0 |
3/11 |
–2/11 |
|
0 |
x2 |
8 |
0 |
1 |
0 |
–2/11 |
5/11 |
|
|
z |
61 |
0 |
0 |
0 |
1 |
1 |
|
Исходное опорное решение
x1 = (0, 0, 45, 31, 30)
z1 = 0
В оценочной строке две отрицательные оценки: –7, –5. Выбираем в качестве разрешающего столбец, соответствующий х1, т.к. оценка этого столбца (–7) наименьшая отрицательная оценка. Разрешающая строка выбирается по
min 15, |
31 |
,15 |
31 |
, |
|
5 |
5 |
||||
|
|
|
этот минимум достигается для 2-й строки. Итак, в базис вводим х1, выводим из базиса х4. В результате первого шага получаем второе опорное решение
|
|
|
31 |
|
132 |
|
88 |
|
||
x2 |
= |
,0, |
,0, |
; |
||||||
|
|
|
|
|||||||
|
|
5 |
|
5 |
|
5 |
|
z2 = 2175 .
После выполнения 2-го шага получаем оптимальное решение:
хопт = (3, 8, 4, 0, 0); zmax = 61
Дальнейшее увеличение z невозможно, т.к. все оценки стали неотрицательными.
Оптимальное решение исходной задачи получается отбрасыванием из Х опт компонент, связанных с балансовыми переменными х3, х4, х5, т.е.
х*опт = (3,8).
При этом значение zmax не изменится.
Теперь дадим геометрическую интерпретацию задачи. Рассмотрим систему неравенств, определяющих множество допустимых планов:
3х1 + 4х2 |
45, |
|
||
5х1 + 2х2 |
31, |
|
||
2х1 + 3х2 |
30. |
|
||
х1 0; x2 |
0. |
|
||
Построим граничную прямую: |
|
|
|
|
3х1 + 4х2 = 45 |
|
|
|
|
|
х1 |
|
0 |
45/3 |
|
х2 |
|
45/4 |
0 |
10
Прямая 3х1 + 4х2 = 45 плоскость ХОУ разделила на две части. Чтобы определить полуплоскость, точки которой удовлетворяют неравенству 3х1 + 4х2 < 45, следует ''испытать'' одну точку. Проще подставить 0 (0,0).
Получим верное неравенство: 0<45. Следовательно, полуплоскость включает точку 0 (0,0). Этот факт отмечается стрелочками.
Определяем положение полуплоскостей, отвечающих каждому неравенству и находим пересечение этих полуплоскостей. Два последних условия в системе ограничений означают, что допустимые планы принадлежат неотрицательному квадрату. Тем самым областью решения системы является четырехугольник ОАВС (рис. 1).
А |
В( ) |
N
Рис. 1. Иллюстрация графического метода Линии уровня целевой функции z задаются уравнением
7х1 + 5х2 = const.
Легко видеть, что они образуют семейство параллельных прямых. Вектор N = (7, 5) называется целевым, он перпендикулярен линиям уровня. Этот вектор указывает направление, двигаясь в котором, мы переходим от меньших значений z к большим, т.е. он указывает направление возрастания функции z. Вершина многоугольника, через которую проходит последняя линия уровня, даст наибольшее значение целевой функции. На рисунке видно, что максимальное значение будет достигнуто в вершине В. Найдем координаты точки В. Эта точка лежит на пересечении прямых
5х1 + 2х2С= 31, 2х1 + 3х2 = 30.
Решая систему из двух уравнений с двумя неизвестными, находим, что
О
точка В имеет координаты х1 = 3, х2 = 8. Подставляя в целевую функцию найденные значения, получим: zmax 7 3 5 8 61.