РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

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

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

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.

Так как при решении задачи на 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^*

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

Повторяя пункты 3 - 5, получим следующие таблицы:

Так как все симплекс-разности положительны, то оптимальное решение найдено:

X = (7/2, 3/4, 11/4, 0, 0) (единиц)

max F = 9 1/4 (рублей)