Реферат: Решение задач симплексным методом
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 )
при наличии ограничений :