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

 

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

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

 

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

 

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

 

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

 

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

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

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

1234	Поделиться:

Воспользуйтесь поиском по сайту: