Postanovka zadachi

  • 07 дек. 2011 г.
  • 1384 Слова
Постановка задачи

Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А идёт времени, часов : оборудованием 1-го типа - а1 , оборудованием 2-го типа - а2 , оборудованием 3-го типа - а3 . На производство единицы изделия В идёт времени, часов : оборудованием 1-го типа - b1 , оборудованием 2-го типа - b2 ,, оборудованием3-го типа - b3 .
На изготовление всех изделий администрация предприятия может предоставить оборудование 1-го типа не более, чем на t1 , оборудование 2-го типа не более, чем на t2 , оборудование 3-го типа не более, чем на t3 часов.
Прибыль от реализации единицы готового изделия А составляет  рублей, а изделия В -  рублей.
Составить план производства изделий А и В, обеспечивающий максимальнуюприбыль от их реализации. Решить задачу простым симплекс-методом. Дать геометрическое истолкование задачи, используя для этого её формулировку с ограничениями-неравенствами.
а1 = 1 b1 = 5 t1 = 10  = 2
а2 = 3 b2 = 2 t2 = 12  = 3
а3 = 2 b3 = 4 t3 = 10

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


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

На произв-во изделия А, часов На произв-воизделия 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 .

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. Заполняетсяисходная симплекс-таблица и рассчитываются симплекс-разности по формулам :
0 = - текущее значение целевой функции
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
 0 -2 -3 0 0 0

Так как при решении задачи на max не все симплекс-разности положительные, то оптимальное решение можно улучшить.
4.Определяем направляющий столбец j*. Для задачи на max он определяется минимальной отрицательной симплекс-разностью. В данном случае это вектор А2
5. Вектор i*, который нужно вывести из базиса, определяется по отношению :
min при аi j > 0

В данном случае сначала это А3 .
5. Заполняется новая симплекс-таблица по исключеню Жордана - Гаусса :
а). направляющую строку i*...
tracking img