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

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

 

 

 

 

 

 

 

 

 

 

 

Глава II

 

2.2 Симплексный метод

 

Математическое программирование занимается изучение экстремальных  задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом : найти экстремум некоторой функции многих переменных f ( x₁, x₂, ... , x_n ) при ограничениях g_i ( x₁, x₂, ... , x_n ) * b_i , где g_i - функция, описывающая ограничения, * - один из следующих знаков £ , = , ³ , а b_i - действительное число, i = 1, ... , m. f называется функцией цели ( целевая функция ).

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

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

при условии :

a₁₁ x₁ + a₁₂ x₂ + . . . + a_1n x_n £ b₁ ;

  a₂₁ x₁ + a₂₂ x₂ + . . . + a_2n x_n £ b₂ ;

_{. . . . . . . . . . . . . . . . . . . . . . . . . . . .}

a_m1 x₁ + a_m2 x₂ + . . . + a_mn x_n £ b_m ;

 x₁ ³ 0, x₂ ³ 0, _{. . .} , x_n ³ 0 _.

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

 

В матричной форме  задачу линейного программирования записывают следующим образом. Найти max c^T x

при условии

A x £ b ;

x ³ 0 ,

где А - матрица ограничений  размером ( m´n), b^(m´1) - вектор-столбец свободных членов, x^{(n ´ 1)} - вектор переменных, с^Т = [c₁, c₂, ... , c_n ] - вектор-строка коэффициентов целевой функции.

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

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

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

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

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

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

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

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

 

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

 

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

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

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

 Если в исходной  системе ограничений присутствовали  знаки “ равно ” или “  больше либо равно ”, то в указанные ограничения добавляются

искусственные переменные, которые так же вводятся и в  целевую функцию со знаками, определяемыми  типом оптимума.

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

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

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

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

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

 

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

 

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

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

 

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

 

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

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

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

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

Постановка задачи

 

 Для производства  двух видов изделий А и В  используется три типа технологического  оборудования. На производство единицы  изделия А идёт времени, часов : оборудованием 1-го типа - а₁ , оборудованием 2-го типа - а₂ , оборудованием 3-го типа - а₃ . На производство единицы изделия В идёт времени, часов : оборудованием 1-го типа - b₁ , оборудованием 2-го типа - b₂ ,_, оборудованием 3-го типа - b₃ .

На изготовление всех изделий администрация предприятия может предоставить оборудование 1-го типа не более, чем на t₁ , оборудование 2-го типа не более, чем на t₂ , оборудование 3-го типа не более, чем на t₃ часов.

Прибыль от реализации единицы  готового изделия А составляет a рублей, а изделия В - b рублей.

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

а₁ = 1 b₁ = 5 t₁ = 10 a = 2

а₂ = 3 b₂ = 2 t₂ = 12 b = 3

а₃ = 2 b₃ = 4 t₃ = 10

 

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

 

 

Построение математической модели задачи

 

	На произв-во изделия  А, часов	На произв-во изделия B, часов	Предпр-е предоставит, часов
Оборуд-е 1го типа	1	5	10
Оборуд-е 2го типа	3	2	12
Оборуд-е 3го типа	2	4	10
Прибыль от реализации, за ед. изд-я	2	3

Построение математической модели осуществляется в три этапа :

1. Определение переменных, для которых будет составляться  математическая модель.

 Так как требуется  определить план производства  изделий А и В, то переменными  модели будут:

x₁ - объём производства изделия А, в единицах;

  x₂ - объём производства изделия В, в единицах.

2. Формирование целевой  функции.

 Так как прибыль  от реализации единицы готовых изделий А и В известна, то общий доход от их реализации составляет 2x₁ + 3x₂ ( рублей ). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции : определить допустимые значения переменных x₁ и x₂ , максимизирующих целевую функцию F = 2x₁ + 3x₂ .

3. Формирование системы  ограничений.

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

x₁ + 5x₂ £ 10 ; 3x₁ + 2x₂ £ 12 ; 2x₁ + 4x₂ £ 10 .

 Так как объёмы  производства продукции не могут  принимать отрицательные значения, то появляются ограничения неотрицательности  :

x₁ ³ 0 ; x₂ ³ 0 .

 Таким образом,  математическая модель задачи представлена в виде : определить план x₁ , x₂ , обеспечивающий максимальное значение функции :

max F = max ( 2x₁ + 3x₂ )

 при наличии ограничений  :

x₁ + 5x₂ £ 10 ;

3x₁ + 2x₂ £ 12 ;

2x₁ + 4x₂ £ 10 .

x₁ ³ 0 ; x₂ ³ 0 .

 

3.2 Решение задачи вручную

 

Табличный метод ещё  называется метод последовательного  улучшения оценки. Решение задачи осуществляется поэтапно.

1. Приведение задачи  к форме :

x₁ + 5x₂ £ 10 ;

3x₁ + 2x₂ £ 12 ;

2x₁ + 4x₂ £ 10 .

x₁ ³ 0 ; x₂ ³ 0 .

2. Канонизируем систему ограничений :

x₁ + 5x₂ + x₃ = 10 ;

3x₁ + 2x₂ + x₄ = 12 ;

2x₁ + 4x₂ + x₅ = 10 .

x₁ ³ 0 ; x₂ ³ 0 .

A₁ A₂ A₃ A₄ A₅ A₀

3. Заполняется исходная  симплекс-таблица и рассчитываются  симплекс-разности по формулам :

d₀ = - текущее значение целевой функции

d_i = - расчёт симплекс-разностей, где j = 1..6 .

		C	2	3	0	0	0
Б	Cб	A0	A1	A2	A3	A4	A5
A3	0	10	1	5	1	0	0
A4	0	12	3	2	0	1	0
A5	0	10	2	4	0	0	1
	d	0	-2	-3	0	0	0

 

Так как при решении  задачи на max не все симплекс-разности положительные, то оптимальное решение можно улучшить.

4. Определяем направляющий  столбец j^*. Для задачи на max он определяется минимальной отрицательной симплекс-разностью. В данном случае это вектор А₂

5. Вектор i^*, который нужно вывести из базиса, определяется по отношению :

min при а_{i j} > 0

 

В данном случае сначала  это А₃ .

5. Заполняется новая  симплекс-таблица по исключеню  Жордана - Гаусса :

 а). направляющую строку i^* делим на направляющий элемент :

a _{i j} = a _{i j} / a _{i j} , где j = 1..6

 б). преобразование всей оставшейся части матрицы :

a _ij = a_ij - a _{i j} × a_ij , где i ¹ i^* , j ¹ j^*

В результате преобразований получаем новую симплекс-таблицу :

 

 

		C	2	3	0	0	0
Б	Cб	A0	A1	A2	A3	A4	A5
A2	3	2	1/5	1	1/5	0	0
A4	0	8	13/5	0	-2/5	1	0
A5	0	2	6/5	0	-4/5	0	1
	d	6	-7/5	0	3/5	0	0