Математическое моделирование экономических процессов на железнодорожном транспорте

метки: Базис, Переменный, Значение, Задача, Распределение, Необходимо, Допустимый, Перевозка

Использование методов линейного программирования для целей оптимального распределения ресурсов, 1.1 Оптимизация плана перевозок с использованием метода потенциалов

1. Составить допустимый план транспортной задачи, используя метод минимальной стоимости для построения базисного плана с ограничением пропускной способности.

2.Найти оптимальный план транспортной задачи, используя метод потенциалов. Построенный допустимый и оптимальный план должен удовлетворять условиям постановки транспортной задачи:

, i=1,2,3……m (1.1.1) , , j=1,2,3……n (1.1.2) , (1.1.3) , (1.1.4) , Целевая функция задачи , (1.1.5) , 3. Рассчитать целевые функции каждого базисного плана перевозок.

4. Найти экономический эффект от оптимизации. Экономический эффект от оптимизации рассчитывается как разность между целевыми функциями базисного и оптимального планов.

5. Рассчитать матрицу показателей характеристик оптимального плана перевозок транспортной задачи. Характеристики клеток рассчитываются по формуле:

(1.1.6) , 6.Показать варианты альтернативных решений при одной и той же целевой функции или при минимальных от нее отклонениях.

150	150	100	100	100	100	150	150
150	105	150
145
155	160
400	8	110
150

F0=5*150+70*50+75*30+145*10+5*10+95*90+55*70+20*8+100*35+100*30 +30*40+150*20+120*10+30*20= 32960 , Н =

150	150	100	100	100	100	150	150
150	105	150
145
155	160
400	8	110
150

= 32960-80*5=32560 Н25 =

150	150	100	100	100	100	150	150
150	105	150
145
155	160
400	8	110
150

= 32560-65*100=26060 Н27 =

150	150	100	100	100	100	150	150
150	105	150
145
155	160
400	8	110
150

= 26060-40*45=24260 Н32 =

150	150	100	100	100	100	150	150
150	105	150
145
155	160
400	8	110
150

Fопт = 24260-40*5=24060 , Нарушений нет, условия а — е пункта 2 на стр. 3 выполняются, значит, план оптимальный. , Проверка: , F = ?bjvj — ?aiui — ?(vj — ) * xij= (150*30+150*40+100*45+100*40+100*45+100*50+150*50+150*30) — (150*0+145*20+155*20+400*10+150*30) — (50-0-30)*75 — (40-10-8)*20 == 24060 , Экономический эффект от оптимизации: , — Fопт = 33060 — 24060 = 9000 , Матрица показателей характеристик клеток оптимального плана перевозок транспортной задачи

105

0

140

В матрице отклонений один ноль, это означает, что существует только один альтернативный план. Строим альтернативный план.

Оптимальный план

150	150	100	100	100	100	150	150
150	105	150
145
155	160
400	8	110
150

Fопт = 24060

Альтернативный план

150	150	100	100	100	100	150	150
150	105	150
145
155	160
400	8	110
150

Fпс/альт = 24060+0*30 = 24060

1.2 Оптимизация плана транспортной задачи с использованием метода потенциалов на сети,
1.Оптимизировать план, перевозок используя
метод потенциалов , 2. Рассчитать целевую функцию оптимального плана перевозок и найти эффект от оптимизации. , 3. Для небазисных звеньев с ограничением провозной способности рассчитать прокатные оценки. , По некоторым участкам введены ограничения провозной способности: AN=20; CL=20; CD=40; EM=80. , Исходные данные:

A	H
B	J
C	146	K
D	L
E	M
F	N
G	O
P

— = Сij, хij > 0 Hij = (Vj — Ui) — Сij , — ? Сij, хij = 0 , — ? Сij — для насыщенных клеток , F0=13*15+67*12+76*16+16*7+86*4+70*19+17*8+43*8+16*9+7*16+30*17+1*31+40*29+50*15 = 7188 , НFK = , = 7188-15*16 = 6948 , НAN = 7 , = 6948-1*7 = 6941 , НCL = 4 , = 6941-20*4 = 6861 , НBO = 1 , Fопт = 6861-6*1=6855 , 1. Нарушений нет, значит, план оптимальный. , Fопт = 6855 ед. , 2. Эффект от оптимизации: ?F= — Fопт = 7188-6855 = 333 , 3. Прокатные оценки: , = 112 — — 9 = 4

4. Ответ: Поставщик А по оптимальному плану обеспечивает спрос потребителей J, K и N. Поставщик В — спрос потребителей P, O и N. Поставщик C — спрос потребителей K, L, M и Н. Поставщик D — спрос потребителя H. Поставщик E — спрос потребителя L, M. Поставщик F — спрос потребителя K. Поставщик G — спрос потребителя O.

Поиск кратчайшего пути , 1.3 Обобщенная транспортная задача, Задание. Имеется возможность выпуска 5 видов продукции (j=1, j=2, j=3, j=4, j=5) на трех типах оборудования (i=1, i=2, i=3) , 1. Сформировать математическое описание задачи. , 2. Построить первоначальное распределение. , 3. Найти оптимальный план модифицированным методом потенциалов.

4. Выполнить анализ оптимального производственного плана, включая состав и объем выпуска продукции, и состояние использованных ресурсов.

Математическая модель распределительной транспортной задачи состоит в следующем: , Найти: , (1.3.1) , При условии: , , i=1,2,3,..,m (1.3.2) , , j=1,2,3,…,n (1.3.3) , (1.3.4) , Здесь: , i — индекс ресурсов , j — индекс производимой продукции, работы, выполняемых перевозок , xij — количество ресурсов i для продукции j . , cij — расходы (себестоимость) при выполнении работы с привлечением ресурсов i. , — ресурсы с номером i , , — потребность в работе с номером j . , Алгоритм модифицированного метода потенциалов состоит из двух этапов. , На первом этапе осуществляется построение допустимого плана , На втором этапе выполняются итеративные процедуры оптимизации базиса задачи. , Выполняется расстановка потенциалов по базисным элеметам матрицы по формулам: , (1.3.5) , (1.3.6) , Проверка решения на оптимальность. Должны выполняться условия: , (1.3.7) , (1.3.8)

Существует два типа контуров. Первый — замкнутого вида, почти аналогичен контуру, построенному по методу потенциалов при решении обычных транспортных задач. Отличием этого контура служит цепочка (шлейф), которая соединяет элементы контура с базисной клеткой, размещенной в n+1 столбце с резервами ресурсов.

Другой контур — открытого типа, по аналогии с методом разрешающих слагаемых, включает в себя два элемента n+1 столбца с резервами ресурсов.

150	150	150	100	300	R
215	2	2	2	2	1
120	2	1	1	2	2
200	2	1	2	1	2

= 75*10+75*20+65*15+20*30+50*20+50*2+100*35=9325

Н33 = 32,5

350	150	100	150	150	R
215	2	2	2	2	1
120	2	1	1	2	2
200	2	1	2	1	2

= 9325-32,5*20=8675 Н14 = 5

350	150	100	150	150	R
215	2	2	2	2	1
120	2	1	1	2	2
200	2	1	2	1	2

Fопт =8675-5*50=8425

В соответствии с планом полностью израсходованы 1-й и 2-ой ресурсы. Третий ресурс используется не полностью, и его остаток составляет 160 единиц.

Так же можно отметить, что 1, 2 и 4 виды работ осуществляются только за счет использования первого вида ресурсов, вторая работа — за счет первого и третьего вида ресурсов, а пятая работа осуществляется за счет использования второго и третьего вида ресурсов.

Наиболее эффективно используется второй вид ресурсов, его потенциал равен 15, менее эффективно используется 1 и 3 виды ресурсов.

Потенциалы столбцов в распределительных транспортных задачах играют роль индикаторов эффективности производства. Чем меньше потенциал, тем эффективнее производится продукция, и, наоборот. Наименьшие затраты на единицу вырабатываемой продукции имеют первый и третий виды работ, их потенциалы соответственно равны V1=10 V2=12,5 . Наибольших затрат требует пятый вид, чей потенциал равен V5=17,5.

2. Применение методов математической статистики в экономических расчетах

2.1 Расчет параметров регрессионных моделей. Проверка надежности найденных статистических показателей и вариаций изменений.

Одной из главных задач повышения качества планирования является становление достоверных показателей на основе объективных количественных закономерностей, существующих в экономических процессах на транспорте.

Функциональная зависимость между независимой переменной Х и зависимой У состоит в том, что каждому значению Х поставлено в однозначное соответствие определенное значение У. В реальных условиях, когда одновременно действует много факторов, изучаемая связь теряет свою функциональность. Возникает потребность в оценке таких зависимостей иными, статистическими методами.

Одним из признанных методов определения статистической связи являются расчеты на базе линейной модели регрессионного анализа.

Парную регрессионную модель можно представить графиком, где на оси абсцисс откладывается независимая переменная Х, а на оси ординат — независимая У. Линейная регрессия описывается уравнением вида:

где — оцениваниемая величина; , х — независимая переменная; , a и b — параметры выборки.

В основе расчета параметров лежит метод наименьших квадратов с использованием в качестве математической модели нормальной системы уравнений:

Параметры a и b находятся соответствующими алгебраическими преобразованиями и подстановкой: , -где x* , y* — средние значения параметров, число испытаний.

Задание 1. Установить статистическую зависимость между годовым объемом работы по грузообороту (млрд ткм), приняв его за независимую переменную (x) и фондоемкостью перевозок приняв ее за зависимую переменную (Y).

Составить линейную модель вида Yx=a+bx.

Ниже в табл 2.1.1 приведена последовательность действий при построении уравнения регрессии. В последних двух строках приведены значения сумм и средних показателей. В результате применения формул имеем: b = 8,55, — 8,89, и уравнение регрессии: = — 8,89 + 8,55*х.

Таблица 1

n	x	y	x^2	y-Yх	(y-Yх)^2	y^2	y-y*	(y-y*)2
1	9	100	900	68,060	31,940	1020,164	10000	38,33	1469,44
2	880	121	85,160	-5,160	26,626	6400	18,33	336,11
3	9	720	68,060	11,940	142,564	6400	18,33	336,11
4	8	320	59,510	-19,510	380,640	1600	-21,67	469,44
5	4	25,310	-5,310	28,196	400	-41,67	1736,11
6	600	100	76,610	-16,610	275,892	3600	-1,67	2,78
7	6	240	42,410	-2,410	5,808	1600	-21,67	469,44
8	7	280	50,960	-10,960	120,122	1600	-21,67	469,44
9	5	200	33,860	6,140	37,700	1600	-21,67	469,44
800	100	76,610	3,390	11,492	6400	18,33	336,11
100	1300	169	102,260	-2,260	5,108	10000	38,33	1469,44
7	420	50,960	9,040	81,722	3600	-1,67	2,78
Итого	740	6740	891	2136,032	53200	7566,67
х*= 8,25	у*= 61,67

Задание 2. Определить достоверность найденного уравнения линейной регрессионной модели, используя критерий Фишера. , Для использования критерия Фишера(F) устанавливается отношение (з) полной дисперсии (s2y ) к остаточной (s2y, x): , m — число факторов в модели (m =2).

Из расчетов табл 2.1.1 имеем:

В знаменателе число степеней свободы 9, в числителе — 11. Соответствующая критическая точка F-распределения 3,1, что больше значения з. Это значит, что данное уравнение линейной регрессии не достоверно.

2.2 Расчет параметров парной корреляции

В основе расчета коэффициента корреляции и параметров оценивания его надежности лежит метод наименьших квадратов с использованием в качестве математической модели нормальной системы уравнений линейной регрессии. Найденный коэффициент корреляции показывает уровень тесноты связи между исследуемыми факторами. Чем выше значение коэффициента корреляции, тем теснее исследуемая связь. Расчет линейного коэффициента корреляции выполняется по формуле:

Задание 3. Найти значение коэффициента корреляции для проверки статистической зависимость между годовым объемом работы по грузообороту (млрд ткм),(x) и фондоемкостью перевозок (y).

Величина линейного коэффициента корреляции изменяется в диапазоне от до +1. По данным табл. 2.1.1. находим показатели, необходимые для расчета r, подставляя их значения в формулу, имеем:

Задание 4. Определить значимость найденных в задании 3, коэффициентов корреляции. Сделать вывод о доверительности найденных значений, используя таблицу нижних границ значимости коэффициента корреляции с уровнем значимости 0,95.

Линейный коэффициент корреляции r = 0,811208. Полученное нами значение близко к 1, что свидетельствует о тесной связи между исследуемыми факторами, т.е. между годовым объемом работы по грузообороту и фондоемкостью перевозок, и больше соответствующей нижней границы коэффициента корреляции, которая равна 0,576.

потенциал регрессионный симплекс линейный , 2.3 Выравнивание рядов распределений с проверкой гипотезы нормальности по критерию Пирсона на базе эмпирического ряда величин себестоимости железнодорожной перевозки, Задание.

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

Среднее значение ряда рассчитывается по формуле: , Таблица 2

xi*ni	— x*	(xi-x*)2	(xi-x*)2*n	t	j(t)	fi-ni	(fi-ni)2	(fi-ni)2/fi
0,58	0,78	2	0,68	1,36	-1,0601	1,1238	2,2476	-2,51	0,0173	1,74	-0,26	0,0680	0,0391
0,78	0,98	7	0,88	6,16	-0,8601	0,7398	5,1783	-2,03	0,0505	5,09	-1,91	3,6627	0,7201
0,98	1,18	1,08	15,12	-0,6601	0,4357	6,1001	-1,56	0,1181	11,89	-2,11	4,4336	0,3727
1,18	1,38	1,28	25,6	-0,4601	0,2117	4,2337	-1,09	0,2209	22,24	2,24	5,0354	0,2264
1,38	1,58	1,48	44,4	-0,2601	0,0676	2,0295	-0,61	0,3303	33,27	3,27	10,6676	0,3207
1,58	1,78	1,68	67,2	-0,0601	0,0036	0,1445	-0,14	0,3950	39,78	-0,22	0,0465	0,0012
1,78	1,98	1,88	67,68	0,1399	0,0196	0,7047	0,33	0,3778	38,05	2,05	4,1978	0,1103
1,98	2,18	2,08	58,24	0,3399	0,1155	3,2350	0,80	0,2889	29,10	1,10	1,2097	0,0416
2,18	2,38	2,28	54,72	0,5399	0,2915	6,9960	1,28	0,1767	17,80	-6,20	38,4706	2,1616
2,38	2,58	2,48	24,8	0,7399	0,5475	5,4746	1,75	0,0864	8,70	-1,30	1,6781	0,1928
2,58	2,78	2	2,68	5,36	0,9399	0,8834	1,7668	2,22	0,0338	3,40	1,40	1,9727	0,5794
		213		371			38,1108	y=106		211		ч2 =	4,7659

Среднеквадратичное отклонение рассчитывается по формуле: , Нормированное отклонение рассчитывается по формуле:

Теоретическое нормальное распределение нормируется через показатель t, умножением значения функции плотности вероятности ц(t):

на значение величины эмпирического нормированного отклонения: , fi= ц(t)*y.

Сумма найденных теоретических частот Уfi = 211 различаются незначительно с суммой частот эмпирического распределения Уni = 213 , то расхождения фактического распределения с теоретической нормальной кривой распределения носят случайный характер, и гипотеза соответствия экспериментального распределения теоретическому принимается.

В практике статистических расчетов для оценки правомерности гипотезы соответствия фактического распределения нормальному принят критерий «хи-квадрат» иначе говоря, критерий Пирсона:

После определения величины критерия Пирсона рассчитывается число степеней свободы: r=k-3, где k — число интервалов в фактическом распределении. В нашем примере: r=k-3 = — 3 = 8. При заданном уровне значимости 5% предусматривающем 5% ошибку и количестве степеней свободы, равном у нас 8 определяется табличная величина критерия Пирсона, c2= 15.5. Найденное значение в расчетах «хи — квадрат» меньше табличного, т.е. х2 = 4,7659 < 15.5, значит, гипотеза о соответствии эмпирического распределения теоретическому принимается.

3. Общая задача линейного программирования и решение её симплекс-методом У нас имеется возможность выпуска 4 видов продукции (N1, N2, N3, N4) на пяти типах машин (A, B, C, D, E).

Известна прибыль, которую принесет выпуск каждого изделия. Необходимо найти максимум прибыли при формировании производственной программы. Модель общей задачи линейного программирования в общем виде выглядит так: Введем обозначения: i — номер ресурса; j — номер выполняемой работы (производимого изделия); аi — ресурсы с номером i;

• количество ресурсов, затраченное на выпуск ед.продукции с номером i;
• коэффициент целевой функции ил показателя критерия оптимальности;
• количество ресурсов, которое необходимо найти Найти мах F=c1+c2+c3+…cj+…+cn при условиях: a11x1+a12x2+a13x3+…+a1jxj+ …+a1nxn<=b1 a21x1+a22x2+a23x3+…+a2jxj+ …+a2nxn<=b2 a31x1+a32x2+a33x3+…+a3jxj +…+ a3nxn<=b3 …………………………………………………………

ai1x1+ ai2x2+ ai3x3+…+aijxj+…+ ainxn <=bi …………………………………………………………….. an1x1+an2x2+an3x3+…+anjxj+…+annxn<=bn >=0 >=0 >=0 …………………………………………………. ……………………………………… ………….. >=0 >=0 Алгоритм симплекс-метода Алгоритм симплекс- метода состоит из двух этапов. На первом этапе осуществляется построение допустимого плана Шаг 1. Построение канонической формы. Для каждого ограничения вводим

дополнительную переменную.

Шаг 2. Строится базис допустимого плана относительно этих переменных.

Шаг 3. Рассчитываются симплекс — множители

и показатели индексной строки

На втором этапе выполняются итеративные процедуры оптимизации базиса задачи.

Шаг 4. Выполняется проверка решения на оптимальность. Для задач на max целевой функции должно выполняться условие:

Если условие оптимальности не выполняется, переход к шагу 5; иначе получен оптимальный и допустимый план.

Шаг 5. Выбор ключевого столбца. Из показателей индексной строки выбирается значение с наибольшим отклонением от условия оптимальности. Соответствующая переменная на следующей итерации входит в базис задачи. Выбор ключевой строки. Находится минимальное отношение показателей столбцов и aij при условии , что aij ?0

Шаг 6. Выполняются симплекс- преобразования:

,

• значение элемента в новом базисе
• значение элемента ключевой строки в новом базисе
• значение элемента в текущем базисе
• значение элемента ключевой строки в текущем базисе
• значение элемента ключевого столбца в текущем базисе
• значение ключевого элемента в текущем базисе

Найти: F=10×1+8×2+9×3+12×4 max

4×1+2×2+0x3+1×4740

2×1+0x2+2×3+1×4760

2×1+2×2+2×3+0x4770

2×1+2×2+1×3+1×4800

0x1+2×2+2×3+2×4700

х1?0

х2?0

х3?0

х4?0

Шаг 1. Построение канонической формы. Для каждого ограничения вводим >=0 — дополнительную переменную. Поскольку у нас пять ограничений, необходимо ввести пять дополнительных переменных: X5, X6, X7, Х8, Х9. В результате имеем систему уравнений относительно ограничений и неравенств относительно переменных.

Х1 ?0

Х2 ?0

Х3 ?0

Х4 ?0

Х5 ?0

Х6 ?0

Х7 ?0

Х8 ?0

Х9 ?0

Шаг 2. Далее построим базис допустимого плана относительно выбранных нами переменных Х5, Х6, Х7, Х8, Х9. Для этого приравняем к 0 значения переменных Х1,Х2,Х3,Х4. Тогда имеем план выпуска изделий пятого вида в количестве 740 единиц, изделий шестого вида — 760 единиц, седьмого вида — 770 единиц, изделий восьмого вида — 800 единиц, девятого вида — 700 единиц.

Х1=0; X2=0; X3=0; X4=0

X5=740; X6=760; X7=770; X8=800; X9=700

На основе базиса допустимого плана построим специальную форму для решения задачи симплекс-методом (таблица 4.1).

Здесь в столбце приведены показатели целевой функции переменных, входящих в базис задачи: с5=0, с6=0, с7 =0, с8=0, с9=0. — наименования самих показателей, X5, X6, X7, Х8, Х9. В столбце приведены значения показателей: X5=740; X6=760; X7=770; X8=800; X9=700. Первая строка таблицы содержит значения показателей . Вторая строка содержит наименования переменных канонической формы. Последняя — индексная строка содержит данные коэффициентов, рассчитываемых на шаге zj-cj.

Таблица 3. Итерация 1

Сi	8	9	0	0	0	0	0
0	740	4	2	0	1	1	0	0	0	0
0	760	2	0	2	1	0	1	0	0	0
0	770	2	2	2	0	0	0	1	0	0
0	800	2	2	1	1	0	0	0	1	0
0	700	0	2	2	2	0	0	0	0	1
Zj-cj	F=0	-10	-12	0	0	0	0	0

Шаг 3. Рассчитываются симплекс — множители (zj ) и показатели индексной строки zj-cj,: где рассчитывается по формуле:

Шаг 4. Выполняется проверка решения на оптимальность. В нашей таблице условие оптимальности не выполняется, значения выделены курсивом.

На шаге 5 выполняется выбор ключевого столбца. По данным индексной строки выбираем показатель z1-c1=-12, как имеющий наибольшее отклонение от условия оптимальности. Это ключевой столбец. Соответствующая переменная, X4, на следующей итерации войдет в базис задачи. Теперь выберем ключевую строку из отношения: Mин{xi/ai1}={740/1; 760/1; 800/1; 700/2}=700/2. Следовательно, строка с переменной является ключевой. Клетка на пересечении ключевой строки Х9 и ключевого столбца называется ключевой. Ее значение равно 2. Теперь необходимо ввести переменную в базис задачи и вывести переменную x9.

Шаг 6. Далее на итерации 1 выполняются симплекс — преобразования. Начнем преобразование полученной таблицы с клеток ключевой строки . Все ее элементы разделим на значение, равное 2, ключевой клетки. Все элементы ключевого столбца всегда равны 0, кроме значения ключевой клетки, которая равна 1.

Полученные значения в таблице 4.2.

Таблица 4. Итерация 2

Сi	8	9	0	0	0	0	0
0	390	4	1	0	1	0	0	0	-1/2
0	410	2	1	0	0	1	0	0	-1/2
0	770	2	2	2	0	0	0	1	0	0
0	450	2	1	0	0	0	0	0	1	-1/2
350	0	1	1	1	0	0	0	0	1/2
Zj-cj	4200	-10	4	3	0	0	0	0	0	6

Таблица 5. Итерация 3

Сi	8	9	0	0	0	0	0
195/2	1	1/4	-1/4	0	1/4	0	0	0	-1/8
0	215	0	-1/2	3/2	0	-1/2	1	0	0	-1/4
0	575	0	3/2	5/2	0	-1/2	0	1	0	1/4
0	255	0	1/2	1/2	0	-1/2	0	0	1	-1/4
350	0	1	1	1	0	0	0	0	1/2
Zj-cj	5175	0	13/2	1/2	0	5/2	0	0	0	19/4

В нашей таблице условие оптимальности для показателей индексной строки относительно всех переменных выполняется. Получен оптимальный план.

По полученному оптимальному плану необходимо выпускать изделия первого (х1), второго (х2), третьего (х3), четвертого (х4) видов в количестве 195/2, 0, 0 и 350 единиц соответственно. Это обеспечивает массу прибыли в 5175 стоимостных единиц.

Подставим значения наших неизвестных в оптимальном плане в систему неравенств модели. Имеем:

4195/2+20+00+1350=740

2195/2+00+203+1350760

2195/2+20+20+0350770

2195/2+20+10+1350800

0195/2+20+20+2350=700

Первое и последнее неравенства выполняются как равенства, это значит, что ресурсы используются полностью. Значения переменных х6=215, х7=575 и х8=255 указывает на то, что ресурсы второго, третьего и четвертого типа машин используются не полностью.

Рассмотрим теперь показатели индексной строки.

Если переменная находится в базисе оптимального плана, то значение коэффициента в индексной строке равно 0. Экономический смысл этих показателей выражается в потерях, которые может иметь производство, если захочет изготавливать соответствующие изделия.

В нашем оптимальном плане коэффициенты индексной строки равны 0.

Коэффициенты в индексной строке для дополнительных переменных характеризуют эффективность используемых ресурсов и называются двойственными, или объективно обусловленными оценками ресурсов. В нашем оптимальном плане для значение в индексной строке равно 5/2, Y6=Y7=Y8= 0, а = 19/4. Чем выше оценка, тем эффективнее используется ресурс. Двойственная оценка характеризует прирост прибыли на единицу прироста соответствующего ресурса.

Двойственная задача:

Двойственная задача: F1=740y1+760y2+770y3+800y4+700y5min 4y1+2y2+2y3+2y4+0y510 2y1+0y2+2y3+2y4+2y58 0y1+2y2+2y3+1y4+2y59 1y1+1y2+0y3+1y4+2y512 0 0 0 0 0 y1=5/2 y2=0 y3=0 y4=0 y5=19/4 F1=740*5/2+760*0+770*0+800*0+ +700*19/4 = 5175 45/2 +20+20+20+019/4=10 25/2+00+20+20+219/48 (13/2) 05/2 +20+20+10+219/49 (1/2) 15/2 +10+00+10+219/4=12

Прямая задача: F=10×1+8×2+9×3+12×4 max 4×1+2×2+0x3+1×4740 2×1+0x2+2×3+1×4760 2×1+2×2+2×3+0x4770 2×1+2×2+1×3+1×4800 0x1+2×2+2×3+2×4700 х1 ?0 х2 ?0 х3 ?0 х4?0 x1=195/2 x2=0 x3=0 x4=350 F=10*195/2+8*0+9*0+12*350= =5175

Матричный вид:

x=BЇ№b

Х = * =

План оптимален

Проверка устойчивости:

Х =* =

Проведение проверки устойчивости показывает то, что данная система относительно устойчива при изменении ресурсов.
, 3.1 Модифицированный симплекс

Имеется возможность выпуска 3 видов продукции (N1, N2, N3) на пяти типах машин (А, В, С, Д, Е).

Сюда занесем значения коэффициентов функции цели, наименования неизвестных, массив значений коэффициентов затрат — выпуск.

Таблица 6

8	9	0	0	0	0	0
Х1	Х2	Х3	Х4	Х5	Х6	Х7	Х8	Х9
5/2	0	0	4	2	0	1	1	0	0	0	0
0	0	0	2	0	2	1	0	1	0	0	0
0	0	0	2	2	2	0	0	0	1	0	0
0	0	0	2	2	1	1	0	0	0	1	0
19/4	6	0	0	2	2	2	0	0	0	0	1
— 8	— 9	0	0	0	0	0
-10	4	3	0	0	0	0	0	6
0	13/2	1/2	0	5/2	0	0	0	19/4

Таблица 6. Итерация 1

Сб	Баз.	Х0	1	1	0	1	2
0	Х5	740	1	0	0	0	0	1
0	Х6	760	0	1	0	0	0	1
0	Х7	770	0	0	1	0	0	0
0	Х8	800	0	0	0	1	0	1
0	Х9	700	0	0	0	0	1	2
0	0	0	0	0	0

Таблица 7. Итерация 2

Сб	Баз.	Х0	4	2	2	2	0
0	Х5	390	1	0	0	0	-1/2	4
0	Х6	410	0	1	0	0	-1/2	2
0	Х7	770	0	0	1	0	0	2
0	Х8	450	0	0	0	1	-1/2	2
Х4	350	0	0	0	0	1/2	0
4200	0	0	0	0	6

Таблица 8. Итерация 3

Сб	Баз.	Х0
Х1	195/2	1/4	0	0	0	-1/8
0	Х6	215	-1/2	1	0	0	-1/4
0	Х7	575	-1/2	0	1	0	1/4
0	Х8	255	-1/2	0	0	1	-1/4
Х4	350	0	0	0	0	1/2
5175	5/2	0	0	0	19/4

3.2 Решение задачи симплекс — методом с использованием искусственного базиса

1. Необходимо составить оптимальную диету, запустив три вида продуктов В1, В2, В3 с заданными ценами С1, С2, С3. Составления диета должна удовлетворять по объему требуемых питательных веществ на уровни не ниже заданного и быть минимальной по затратам.

1. Сформировать математическое описание задачи. , 2. Построить каноническую форму, искусственный базис и получить допустимое решение. , 3. Найти оптимальный план.

4. Выполнить анализ оптимального плана, включая состав и объем закупленных продуктов, расходы, эффективность и состояние питательных веществ.

Алгоритм симплекс — метода в задаче с искусственным базисом также состоит из двух этапов. На первом осуществляется построение канонической формы — допустимого плана с использованием искусственного базиса. При этом дополнительные неизвестные имеют знак “-” , а их коэффициенты в целевой функции равны нулю, а искусственные переменные имеют знак “+” , а их коэффициенты в целевой функции равны достаточно большому числу М. На втором этапе выполняется обычная оптимизационная процедура.

Шаг 1. Построение канонической формы. Для каждого ограничения вводим: , ?0 — дополнительную переменную; , ?0 — переменную искусственного базиса. , Шаг 2. Строится базис допустимого плана относительно переменных искусственного базиса , Шаг 3. Рассчитываются симплекс — множители и показатели индексной строки: , Шаг 4. Выполняется проверка решения на оптимальность. Для задач на min целевой функции должно выполняться условие: , Если условие оптимальности не выполняется, переход к шагу 5; иначе получен оптимальный и допустимый план.

Шаг 5. Выбор ключевого столбца. Из показателей индексной строки выбирается значение с наибольшим отклонением от условия оптимальности. Соответствующая переменная на следующей итерации входит в базис задачи.

Шаг 6. Выбор ключевой строки. Находится минимальное отношение показателей столбцов и aij, при условии, что , Шаг 7. Выполняются симплекс — преобразования , Найти: F = 5×1 + 2×2 + 4×3 min , 0x1 + 2×2 + 1×3 ? , 2×1 + 4×2 + 0x3 ? , 10×1 + 4×2 + 2×3 ? , х1?0 , х2?0 , х3?0 , х4?0 , Шаг 1. Построение канонической формы. Для каждого ограничения вводим: ?0 — дополнительную переменную; , ?0 — переменную искусственного базиса.

. Поскольку у нас 3 ограничения, необходимо ввести 3 дополнительных переменных: X4, X6, X8; и 3 переменных искусственного базиса: X5, X7, X9. В результате имеем систему уравнений относительно ограничений и неравенств относительно переменных.

F = 5×1 + 2×2 + 4×3 — 0х4 — 0х5 -0х6 +Мх7 +Мх8+Мх9 min

Х1 ?0

Х2 ?0

Х3 ?0

Х4 ?0

Х5 ?0

Х6 ?0

Х7 ?0

Х8 ?0

Х9 ?0

Шаг 2. Далее построим базис допустимого плана относительно выбранных нами переменных искусственного базиса Х5, Х7, Х9. Для этого приравняем к 0 значения остальных переменных. Тогда имеем план объема питательных веществ для седьмого вида продукта в количестве единиц, восьмого вида — единиц, девятого вида — единиц.

Х1=0; X2=0; X3=0;

X7=25; X8=25; X9=10

На основе базиса допустимого плана построим специальную форму для решения задачи симплекс-методом (таблица 5.1).

Здесь в столбце приведены показатели целевой функции переменных, входящих в базис задачи. — наименования самих показателей: X7, X8, Х9. В столбце приведены значения показателей: X7=25, =25, Х9=10. Первая строка таблицы содержит значения показателей . Вторая строка содержит наименования переменных канонической формы. Последние две строки — индексные строки, которые содержат данные коэффициентов, рассчитываемых на шаге zj-cj.

Таблица 9. Итерация 1

Сi	5	2	4	0	0	0	М	М	М
М	Х7	0	2	1	0	0	1	0	0
М	Х8	2	4	0	0	0	0	1	0
М	Х9	4	2	0	0	0	0	1
60М	12М	10М	3М	-М	-М	-М	0	0	0
0	0	0	0	0	0	0

Таблица 10. Итерация 2

Сi	5	4	2	0	0	0	М	М	М
М	Х7	0	2	1	0	0	1	0	0
М	Х8	0	16/5	-2/5	0	1/5	0	1	-1/5
5	Х1	1	1	2/5	1/5	0	0	-1/10	0	0	1/10
48М	0	26/5М	3/5М	-М	-М	1/5М	0	0	-6/5М
5	0	0	0	0	-1/2	0	0	1/2

Таблица 11. Итерация 3

Сi	5	4	2	0	0	0	М	М	М
М	Х7	0	0	0	1/2	1	0	-1/2
М	Х8	0	0	1	0	1
2	Х2	5/2	5/2	1	1/2	0	0	-1/4	0	0	1/4
35М	-13М	0	-2М	-М	-М	3/2М	0	0	-5/2М
5	0	0	0	0	-1/2	0	0	1/2

Таблица 12. Итерация 4

Сi	5	4	2	0	0	0	М	М	М
М	Х7	25/2	0	1	1/2	0	1	-1/2	0
0	Х6	0	0	1	0	1
2	Х2	25/4	1/2	1	0	0	-1/4	0	0	1/4	0
25/2М	-М	0	М	-М	1/2М	0	0	-3/2М	-М
25/2	0	0	-1/2	0	0	1/2	0

Таблица 13. Итерация 5

Сi	5	4	2	0	0	0	М	М	М
4	Х3	25/2	0	1	1/2	0	1	-1/2	0
0	Х6	-10	0	0	0	1	2	0
2	Х2	25/4	1/2	1	0	0	-1/4	0	0	1/4	0
0	0	0	0	0	0	0	-М	-М	-М
125/2	0	0	3/2	0	2	-3/2	0

Таблица 14. Итерация 6

Сi	5	4	2	0	0	0	М	М	М
0	Х5	0	2	1	0	2	0
0	Х6	-10	0	0	0	1	2	0
2	Х2	25/2	0	1	1/2	-1/2	0	0	1/2	0	0
0	0	0	0	0	0	0	-М	-М	-М
0	0	0	1	0	0

В нашей таблице условие оптимальности для показателей индексной строки относительно всех переменных выполняется. Получен оптимальный план.

По полученному оптимальному плану необходимо закупить продукты первого (х1), второго (х2), третьего (х3), видов в количестве 0, 25/2 и 0 единиц соответственно. Это обеспечивает расход в стоимостных единиц.

Подставим значения наших неизвестных в оптимальном плане в систему неравенств модели. Имеем:

00+225/2+10 =

20+425/2+00 >

100+425/2+20 >

Первое неравенство выполняется как равенство, это значит, что куплен первый продукт с максимальным количеством питательных веществ. Значение переменной Х5=25 и Х6=40 указывает на то, что продукты второго и третьего вида куплены с недостаточными количествами питательных веществ для оптимальной диеты.

Список литературы 1. Карчик В.Г. Математические методы в планировании и управлении на железнодорожном транспорте: Учебное пособие. Часть вторая — Л.:ЛИИЖТ 2. Математическое моделирование экономических процессов на железнодорожном транспорте.: Учебник для ВУЗов/ Под ред. А.Б. Каплана. — М.: Транспорт, 1984 3. Кочович Е. Финансовая математика. — М. Перспектива, 1994. 4. Гольштейн Е.Г. Задачи линейного программирования транспортного типа. — М.:Наука, 1969

Карчик В.Г. Математическое моделирование экономических процессов на железнодорожном транспорте. — СПб.: Издательство “Милена”, 2001