--PAGE_BREAK--1.2 Табличный симплекс — метод
Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b — положительны.
Алгоритм решения сводится к следующему :
Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.
Если в исходной системе ограничений присутствовали знаки “ равно ” или “ больше либо равно ”, то в указанные ограничения добавляются
искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.
Формируется симплекс-таблица.
Рассчитываются симплекс-разности.
Принимается решение об окончании либо продолжении счёта.
При необходимости выполняются итерации.
На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.
1.3 Метод искусственного базиса
Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m, а в задачи минимизации — с положительными m. Таким образом из исходной получается новая m— задача.
Если в оптимальном решении m— задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении m— задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
1.4 Модифицированный симплекс — метод
В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы.
В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Хорош для ситуаций, когда число переменных n значительно превышает число ограничений m.
В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс-разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана-Гаусса.
Особенности заключаются в наличии двух таблиц — основной и вспомагательной, порядке их заполнения и некоторой специфичности расчётных формул.
2.СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А идёт времени, часов: оборудованием 1-го типа — а1, оборудованием 2-го типа — а2, оборудованием 3-го типа — а3.На производство единицы изделия В идёт времени, часов: оборудованием 1-го типа — b1, оборудованием 2-го типа — b2 ,, оборудованием 3-го типа — b3 .
На изготовление всех изделий администрацияпредприятия может предоставить оборудование 1-го типа не более, чем на t1, оборудование 2-го типа не более, чем на t2, оборудование 3-го типа не более, чем на t3 часов.
Прибыль от реализации единицы готового изделия А составляет aрублей, а изделия В — bрублей.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу простым симплекс-методом. Дать геометрическое истолкование задачи, используя для этого её формулировку с ограничениями-неравенствами.
а1 = 1 b1 = 5 t1 = 10 a= 2
а2 = 3 b2 = 2 t2 = 12 b= 3
а3 = 2 b3 = 4 t3 = 10
3.РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ 3.1 Построение математической модели задачи
На произв-во изделия А, часов
На произв-во изделия B, часов
Предпр-е предоставит, часов
Оборуд-е 1го типа
1
5
10
Оборуд-е 2го типа
3
2
12
Оборуд-е 3го типа
2
4
10
Прибыль от реализации, за ед. изд-я
2
3
Построение математической модели осуществляется в три этапа :
1. Определение переменных, для которых будет составляться математическая модель.
Так как требуется определить план производства изделий А и В, то переменными модели будут:
x1 — объём производства изделия А, в единицах;
x2 — объём производства изделия В, в единицах.
2. Формирование целевой функции.
Так как прибыль от реализации единицы готовых изделий А и В известна, то общий доход от их реализации составляет 2x1 + 3x2 ( рублей ). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции: определить допустимые значения переменных x1 и x2, максимизирующих целевую функцию F = 2x1 + 3x2 .
3. Формирование системы ограничений.
При определении плана производства продукции должны быть учтены ограничения на время, которое администрация предприятия сможет предоставить на изготовления всех изделий. Это приводит к следующим трём ограничениям :
x1 + 5x2 £10;3x1 + 2x2 £12; 2x1 + 4x2£10 .
Так как объёмы производства продукции не могут принимать отрицательные значения, то появляются ограничения неотрицательности :
x1 ³0; x2³0 .
Таким образом, математическая модель задачи представлена в виде: определить план x1, x2, обеспечивающий максимальное значение функции :
max F = max ( 2x1 + 3x2 )
при наличии ограничений :
x1 + 5x2 £10;
3x1 + 2x2 £12;
2x1 + 4x2£10 .
x1 ³0; x2³0 .
продолжение
--PAGE_BREAK--3.2 Решение задачи вручную
Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.
1. Приведение задачи к форме :
x1 + 5x2 £10;
3x1 + 2x2 £12;
2x1 + 4x2£10 .
x1 ³0; x2³0 .
2. Канонизируем систему ограничений :
x1 + 5x2 + x3 =10;
3x1 + 2x2 + x4 = 12;
2x1 + 4x2 + x5 = 10 .
x1 ³0; x2³0 .
A1 A2 A3 A4 A5 A0
3. Заполняется исходная симплекс-таблица и рассчитываются симплекс-разности по формулам :
d= — текущее значение целевой функции
C
2
3
Б
Cб
A0
A1
A2
A3
A4
A5
A3
10
1
5
1
A4
12
3
2
1
A5
10
2
4
1
d
-2
-3
di= — расчёт симплекс-разностей, где j = 1..6 .
Так как при решении задачи на max не все симплекс-разности положительные, то оптимальное решение можно улучшить.
4. Определяем направляющий столбец j*. Для задачи на max он определяется минимальной отрицательной симплекс-разностью. В данном случае это вектор А2
5. Вектор i*, который нужно вывести из базиса, определяется по отношению :
min при аi j > 0
В данном случае сначала это А3 .
5. Заполняется новая симплекс-таблица по исключеню Жордана — Гаусса :
а). направляющую строку i* делим на направляющий элемент:
a i j = a i j / a i j, гдеj = 1..6
б). преобразование всей оставшейся части матрицы :
a ij = aij — a i j×aij, гдеi ¹i*, j ¹j*
C
2
3
Б
Cб
A0
A1
A2
A3
A4
A5
A2
3
2
1/5
1
1/5
A4
8
13/5
-2/5
1
A5
2
6/5
-4/5
1
d
6
-7/5
3/5
В результате преобразований получаем новую симплекс-таблицу :
Повторяя пункты 3 — 5, получим следующие таблицы :
C
2
3
Б
Cб
A0
A1
A2
A3
A4
A5
A2
3
5/3
1
1/3
-1/6
A4
11/3
4/3
1
-13/6
A1
2
5/3
1
-2/3
5/6
d
8 1/3
-1/3
7/6
C
2
3
Б
Cб
A0
A1
A2
A3
A4
A5
A2
3
3/4
1
-1/4
3/8
A3
11/4
1
3/4
-13/8
A1
2
7/2
1
1/2
-1/4
d
9 1/4
1/4
5/8
Так как все симплекс-разности положительны, то оптимальное решение найдено :
X = ( 7/2, 3/4, 11/4, 0, 0 ) ( единиц )
max F = 9 1/4 ( рублей )
продолжение
--PAGE_BREAK--