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

Введение

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f (x1, x2,..., xn) при ограничениях gi (x1, x2,..., xn) bi, где gi - функция, описывающая ограничения, а bi - действительное число, i = 1,..., m. f называется функцией цели (целевая функция).

Линейное программирование - это раздел математического программирования, в котором рассматриваются методы решения экстремальных задач с линейным функционалом и линейными ограничениями, которым должны удовлетворять искомые переменные.

Задачу линейного программирования можно сформулировать так. Найти max при условии:

a11 x1 + a12 x2 +... + a1n xn b1;

a21 x1 + a22 x2 +... + a2n xn b2;

am1 x1 + am2 x2 +... + amn xn ? bm;

x1 0, x2 0,..., xn 0.

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

В матричной форме задачу линейного программировани записывают следующим образом. Найти max cT x при условии A x b; x 0, где А - матрица ограничений размером (m n), b(m 1) - вектор-столбец свободных членов, x(n 1) - вектор переменных, сТ = [c1, c2,..., cn ] - вектор-строка коэффициентов целевой функции.

Решение х0 называется оптимальным, если для него выполняется условие сТ х0 сТ х, для всех х ? R(x).

Поскольку min f(x) эквивалентен max [ - f(x) ], то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

Для решения задач данного типа применяются методы:

1) графический;

2) табличный (прямой, простой) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

Табличный симплекс-метод

Для его применения необходимо, чтобы знаки в ограничениях были вида " меньше либо равно ", а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

1. Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

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

3. Формируется симплекс-таблица.

4. Рассчитываются симплекс-разности.

5. Принимается решение об окончании либо продолжении счёта.

6. При необходимости выполняются итерации.

7. На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

Метод искусственного базиса

Данный метод решения применяется при наличии в ограничении знаков "равно", "больше либо равно", "меньше либо равно" и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами, а в задачи минимизации - с положительными. Таким образом из исходной получается новая - задача.

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

Модифицированный симплекс-метод

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

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

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

Первый этап - Получение задания к курсовой работе

1. Все числовые данные, касающиеся предполагаемых производственных и экономических процессов, берутся на основе шестизначного шифра: 4 6 1 3 9 8

Под каждую цифру записываются буквы a, b, c, d, e, f в следующем виде: 4 6 1 3 9 8, а b c d e f, из последней строки таблицы индивидуальных заданий находим в столбцы соответствующие буквам a, b, c, d, e, f. Тогда числовыми данными, необходимыми для выполнения данной курсовой работы, будут данные находящиеся в а - том столбце в строке 4, b - том столбце в строке 6, c - том столбце в строке 1, d - том столбце в строке 3, e - том столбце в строке 9 и f - том столбце в строке 8.

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

В моем случае для цифры 4 соответствует вариант 4.

IV - вариант задание

Требуется составить смесь, содержащую четыре химических вещества A, B, C, D. Составленная смесь должна содержать этих химических веществ не менее Pj единиц, где j = A, B, C, D соответственно. Указанные химические вещества содержаться в трех видах продуктов I, II, III в концентрации указанной в таблицах № 3.4.1 - 3.4.10

Стоимость используемых продуктов известна и она равна Si, i = 1, 2, 3.

Требуется найти оптимальный план, обеспечивающий минимальную стоимость используемых продуктов.

Последующие числовые данные берутся только из таблицы исходных данных выбранного варианта задания т.е. из таблицы № 3.4.11.

2. По столбцу таблицы № 3.4.11 для строки 6 исходной таблицей времени, необходимого для обработки каждого из изделий на указанных машинах, будет таблица № 3.4.6 т.е. следующая таблица:



Вещества Продукт	A	B	C	D
I	3	4	1	2
II	5	4	2	3
III	4	1	3	5

3. По столбцу c - на первой строке находим P1 = 10, S1 = 20

4. По столбцу d - на третьей строке определяем P2 = 19, S2 = 44

5. По столбцу e - по строке девять установим, что P3 = 14, S3 = 41

6. По столбцу f - определим по восьмой строке Р4 = 21

Второй этап - Составление математической модели задачи

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

Вещества Продукт	A	B	C	D	Pj
I	3	4	1	2	20
II	5	4	2	3	44
III	4	1	3	5	41
Si	10	19	14	21

Через Х1 обозначим продукт I вида.

Через Х2 обозначим продукт II вида.

Через Х3 обозначим продукт III вида.

2. Обращаясь к условиям задачи определяем все возможные ограничения объединяя их в систему ограничений.



Система ограничений 1

При этом общая прибыль определяется выражением:

F = 20X1 + 44X2 + 41X3

- т.е. получим некоторую целевую функцию 2

Таким образом, по условию задачи требуется из множества допустимых решений системы ограничений 1 определить такое решение, которое максимизирует целевую функцию 2.

Все выражения в системе ограничений 1 и целевой функции 2 являются линейными. По - этому данная задача является задачей линейного программирования.

Для решения задачи линейного программирования применяется симплекс - метод.

Третий этап - выбор метода решения полученной математической задачи

Для решения задач линейного программирования симплекс - методом задача приводиться к каноническому виду:



Fmax = 20X1 + 44X2 + 41X3

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

fmin = -20X1 - 44X2 - 41X3

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
	3	5	4	-1	0	0	0	10
	4	4	1	0	-1	0	0	19
	1	2	3	0	0	-1	0	14
	2	3	5	0	0	0	-1	21
f	-20	-44	-41	0	0	0	0	0

А) Выбираем разрешающий элемент по строке 1 - Х2. Соответственно вся строка делиться на 5. Все остальные элементы находятся по правилу прямоугольника.

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
	3	5	4	-1	0	0	0	10
	4	4	1	0	-1	0	0	19
	1	2	3	0	0	-1	0	14
	2	3	5	0	0	0	-1	21
f	-20	-44	-41	0	0	0	0	0
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х2	3/5	1	4/5	-1/5	0	0	0	2
	8/5	0	-11/5	4/5	-1	0	0	11
	-1/5	0	7/5	2/5	0	-1	0	10
	1/5	0	13/5	3/5	0	0	-1	15
f	-8/5	0	-9/5	-9/5	0	0	0	- 88

Б) Выбираем разрешающий элемент по строке 1 - Х3. Соответственно вся строка делиться на 4/5. Все остальные элементы находятся по правилу прямоугольника.

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
	3/5	1	4/5	-1/5	0	0	0	2
	8/5	0	-11/5	4/5	-1	0	0	11
	-1/5	0	7/5	2/5	0	-1	0	10
	1/5	0	13/5	3/5	0	0	-1	15
f	-8/5	0	-9/5	-9/5	0	0	0	- 88
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	3/4	5/4	1	-1/4	0	0	0	5/2
	13/4	11/4	0	1/4	-1	0	0	33/2
	-5/4	-7/4	0	3/4	0	-1	0	13/2
	-7/4	-13/4	0	5/4	0	0	-1	17/2
f	-1/4	9/4	0	9/4	0	0	0	- 74

С) Выбираем разрешающий элемент по строке 4 - Х4. Соответственно вся строка делиться на 5/4. Все остальные элементы находятся по правилу прямоугольника.

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	3/4	5/4	1	-1/4	0	0	0	5/2
	13/4	11/4	0	1/4	-1	0	0	33/2
	-5/4	-7/4	0	3/4	0	-1	0	13/2
	-7/4	-13/4	0	5/4	0	0	-1	17/2
f	-1/4	9/4	0	9/4	0	0	0	- 74
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	2/5	3/5	1	0	0	0	-1/5	21/5
	18/5	17/5	0	0	-1	0	1/5	74/5
	-1/5	1/5	0	0	0	-1	3/5	7/5
Х4	-7/5	-13/5	0	1	0	0	-4/5	34/5
f	-17/5	-18/5	0	0	0	0	4/5	- 587/2

Д) Выбираем разрешающий элемент по строке 2 - Х2. Соответственно вся строка делиться на 5/4. Все остальные элементы находятся по правилу прямоугольника.

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	2/5	3/5	1	0	0	0	-1/5	21/5
	18/5	17/5	0	0	-1	0	1/5	74/5
	-1/5	1/5	0	0	0	-1	3/5	7/5
Х4	-7/5	-13/5	0	1	0	0	-4/5	34/5
f	-17/5	-18/5	0	0	0	0	4/5	- 587/2
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	-4/17	0	1	0	3/17	0	-4/17	27/17
Х2	18/17	1	0	0	-5/17	0	1/17	74/17
	-7/17	0	0	0	1/17	-1	10/17	9/17
Х4	23/17	0	0	1	-13/17	0	-11/17	308/17
f	7/17	0	0	0	-1/17	0	27/17	- 4363/17

Е) Выбираем разрешающий элемент по строке 3 - Х7. Соответственно вся строка делиться на 10/17. Все остальные элементы находятся по правилу прямоугольника



Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	-4/17	0	1	0	3/17	0	-4/17	27/17
Х2	18/17	1	0	0	-5/17	0	1/17	74/17
	-7/17	0	0	0	1/17	-1	10/17	9/17
Х4	23/17	0	0	1	-13/17	0	-11/17	308/17
f	7/17	0	0	0	-1/17	0	27/17	- 4363/17
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	-2/5	0	1	0	1/5	-2/5	0	9/5
Х2	11/10	1	0	0	-3/10	1/10	0	43/10
Х7	-7/10	0	0	0	1/10	-17/10	1	9/10
Х4	9/10	0	0	1	-7/10	-11/10	0	187/10
f	12	0	0	0	-5	-12	0	-263

Ж) Выбираем разрешающий элемент по строке 2 - Х1. Соответственно вся строка делиться на 11/10. Все остальные элементы находятся по правилу прямоугольника

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	-2/5	0	1	0	1/5	-2/5	0	9/5
Х2	11/10	1	0	0	-3/10	1/10	0	43/10
	-7/10	0	0	0	1/10	-17/10	1	9/10
Х4	9/10	0	0	1	-7/10	-11/10	0	187/10
f	12	0	0	0	-5	-12	0	-263
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Х6	Х7	Свободный член
Х3	0	4/11	1	0	1/11	-4/11	0	37/11
Х1	1	10/11	0	0	-3/11	1/11	0	43/11
Х7	0	7/11	0	0	-1/11	-18/11	1	40/11
Х4	0	-9/11	0	1	-5/11	-13/11	0	167/11
f	0	-120/11	0	0	19/11	-144/11	0	- 2377/11

Найденное базисное решение (43/11, 0, 37/11, 167/11, 0, 0, 40/11) является оптимальным

f = -2377/11

f = -20X1 - 44X2 - 41X3 = -20*43/11 - 44*0 - 41*37/11 = -2377/11

Ответ: (43/11, 0, 37/11, 167/11, 0, 0, 40/11), f = -2377/11

Четвертый этап - Составление блок схемы решения задачи

Пусть предполагается, что известны значения n и m, lj и ui для задачи, требующей минимизации функции

F x = f (x1,x2,.......xn)

с явными ограничениями:

lj < = xj < = u i при j=1,2,......, n, (1)

а также с неявными ограничениями

g (x1,x2,.......xn) < = bi при i =1,2,.......,m (2)

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

xy = lj + r (uj +lj) (3)

для j=1,2,......, n, и i =2,3,.......,m где r псевдослучайная равномерно распределенная переменная в интервале (0;1). Такая переменная в языке Бейсик может быть задана с помощью оператора Y-RND(X).

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

X1 = (x1 + xc)/2, (4)

i-1

где xc = 1/ i-1 ? xl (5) l=1

Если точка в соотношении (4) все еще не является допустимой, то описанная соотношением процедура повторяется вновь до тех пор, пока точка не станет допустимой.

Пятый этап - Подготовка словесного алгоритма решения задачи

Вводим данные в таблицу

Находим разрешающий элемент:

Берем каждый элемент первой строки и делим на свободный член первой строки.

Находим среди всех деленных элементов минимальный.

Берем каждый элемент второй строки и делим на свободный член второй строки.

Находим среди всех деленных элементов минимальный.

Берем каждый элемент третей строки и делим на свободный член третей строки.

Находим среди всех деленных элементов минимальный.

Берем минимальные элементы первой, второй и третей строки и среди них находим минимальный (это и будет разрешающий элемент).

Вычисляем всю таблицу методом прямоугольника относительно разрешающего элемента:

Умножаем разрешающий элемент на элемент решаемой строки.

Отнимаем произведение соответствующего элемента решаемой строки на элемент разрешающего столбца решаемой строки

И делим ответ на разрешающий элемент.

Делим разрешающую строку на разрешающий элемент.

Берем каждый элемент разрешающей строки и делим на разрешающий элемент.

Всем элементам, кроме разрешающего элемента, разрешающего столбца присвоить (0)

Разрешающему элементу присвоить (1).

В индексе разрешающей строки присвоить индекс разрешающего столбца.

Если на F строке существуют отрицательные элементы то вернутся к пункту если отрицательных нет то перейти к пункту 9.

Проверяем F на оптимальность.

Подставляем в целевую функцию значения из свободного члена с соответствующим индексом.

Складываем все элементы.

Сравниваем ответ целевой функции с элементом свободного члена F строки.

Получаем оптимальный план.

Шестой этап - Разработка программы для решения задачи

Private Sub Form_Load()

Left = (Screen.Width - Width) \ 2

Top = (Screen.Height - Height) \ 2

End Sub

Private Sub Timer1_Timer()

Unload Form1

Load Form2

Form2.Show

End Sub

Объявление переменных

Public a As Integer

Public b As Integer

Public c As Integer

Public d As Integer

Public e As Integer

Public f As Integer

Public aa As Integer

Public ab As Integer

Public ac As Integer

Public ad As Integer

Public ae As Integer

Public af As Integer

Public ba As Integer

Public bb As Integer

Public bc As Integer

Public bd As Integer

Public be As Integer

Public bf As Integer

Public ca As Integer

Public cb As Integer

Public cc As Integer

Public cd As Integer

Public ce As Integer

Public cf As Integer

Public X1 As Integer

Public X2 As Integer

Public X3 As Integer

Public F As Integer

Private Sub Command1_Click()

Определение значения переменных

a = Text1.Text

b = Text2.Text

c = Text3.Text

d = Text4.Text

e = Text5.Text

f = Text6.Text

aa = Text7.Text

ab = Text8.Text

ac = Text9.Text

ad = Text10.Text

ae = Text11.Text

af = Text12.Text

ba = Text13.Text

bb = Text14.Text

bc = Text15.Text

bd = Text16.Text

be = Text17.Text

bf = Text18.Text

ca = Text19.Text

cb = Text20.Text

cc = Text21.Text

cd = Text22.Text

ce = Text23.Text

cf = Text24.Text

X1 = Text25.Text

X2 = Text26.Text

X3 = Text27.Text

Проверка выполнения равенств

If a*x1+aa*x2+ba*x3=ca Then

«Равенство выполняется» Else «Равенство не выполняется»

If b*x1+ab*x2+bb*x3=cb Then

«Равенство выполняется» Else «Равенство не выполняется»

If c*x1+ac*x2+bc*x3=cc Then

«Равенство выполняется» Else «Равенство не выполняется»

If d*x1+ad*x2+bd*x3=cd Then

«Равенство выполняется» Else «Равенство не выполняется»

If e*x1+ae*x2+be*x3=ce Then

«Равенство выполняется» Else «Равенство не выполняется»

F= f*x1+af*x2+bf*x3

If F<fmin Then

«Решение не выполняется» Else «Решение выполняется, план является оптимальным»

Text28.Visible = True

Text29.Visible = True

End Sub

Private Sub Command2_Click()

`очистка текстовых окон для следующего ввода данных

Text1.Text = ""

Text2.Text = ""

Text3.Text = ""

Text4.Text = ""

Text5.Text = ""

Text6.Text = ""

Text7.Text = ""

Text8.Text = ""

Text9.Text = ""

Text10.Text = ""

Text11.Text = ""

Text12.Text = ""

Text13.Text = ""

Text14.Text = ""

Text15.Text = ""

Text16.Text = ""

Text17.Text = ""

Text18.Text = ""

Text19.Text = ""

Text20.Text = ""

Text21.Text = ""

Text22.Text = ""

Text23.Text = ""

Text24.Text = ""

Text25.Text = ""

Text26.Text = ""

Text27.Text = ""

Text28.Visible = False

Text29.Visible = False

End Sub

Private Sub Command3_Click()

`показать справку

Unload Form2

Load Form3

Form3.Show

End Sub

Private Sub Command4_Click()

Unload Form2

End Sub

Private Sub Form_Load()

Left = (Screen.Width - Width) \ 2

Top = (Screen.Height - Height) \ 2

`подготовка текстовых окон к вводу данных при запуске рабочего окна

Text1.Text = ""

Text2.Text = ""

Text3.Text = ""

Text4.Text = ""

Text5.Text = ""

Text6.Text = ""

Text7.Text = ""

Text8.Text = ""

Text9.Text = ""

Text10.Text = ""

Text11.Text = ""

Text12.Text = ""

Text13.Text = ""

Text14.Text = ""

Text15.Text = ""

Text16.Text = ""

Text17.Text = ""

Text18.Text = ""

Text19.Text = ""

Text20.Text = ""

Text21.Text = ""

Text22.Text = ""

Text23.Text = ""

Text24.Text = ""

Text25.Text = ""

Text26.Text = ""

Text27.Text = ""

End Sub

Private Sub Form_Load()

Left = (Screen.Width - Width) \ 2

Top = (Screen.Height - Height) \ 2

End Sub

Private Sub Timer1_Timer()

Unload Form3

Load Form2

Form2.Show

End Sub

Результат использования программы

Ввод начальных коэффициентов

Полученное решение



Список использованной литературы

Кузнецов Ю.Н. и др. « Математическое программирование» Москва, «Высшая школа», 1980 г.

Методические рекомендации «Курсовая работа по моделированию производственных и экономических процессов» Талдыкорган. 1999 г.

Солодовников А.С. « Введение в линейную алгебру и линейное программирование» Москва, «Просвещение», 1996 г.

Уолш Б. « Программирование на Бейсике» Пер. С анг. - Москва:Радио и связь, 1998 г.

Фиакко А., Мак-кормик Г. « Нелинейное программирование» Пер. С анг. - Москва:Мир, 1988 г.