Характеристика типовых задач математического моделирования и подходов к их решению

Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой αr+βs > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min(Xij). Далее составляют новую таблицу по следующему правилу:

• В плюсовых клетках добавляем Х.
• Из минусовых клеток вычитаем Х.
• Все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающую новое решение Х, такое, что F (X1) ≤ F (X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

 

 

2. Практическая часть

 

2.1 Составление математической модели задачи планирования производства

 

Задача. Предприятие предполагает выпускать два вида продукции А1 и А2, для производства которых используется сырьѐ трех видов. Производство обеспечено сырьем каждого вида в количествах: b1, b2, b3 кг. На изготовление единицы изделия А1 требуется затратить сырья каждого вида а11, а21, а31 кг, соответственно, а для единицы изделия А2 – а12, а22, а32 кг. Прибыль от реализации единицы изделия А1 составляет с1 ден.ед., для единицы изделия А2 – с2 ден.ед.

Требуется составить план производства изделий А1 и А2 обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.

 

Таблица 2.1.1

Исходная таблица

Вид сырья	Продукция		Ограничения по сырью
	А1	А2
1-й	4	1	240
2-й	2	3	180
3-й	1	5	251
Прибыль	40	30

 

Математическая модель

Пусть x1-количество изделий А1; Х2-количество изделий А2;

Ограничения:

 

Целевая функция: Z= 40x1 + 30x2 → max

 

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

Найдем область допустимых решений

Посмотрим прямые:

 

4x1+x2=240

2x1+3x2=180

1x1+5x2=251

 

Рисунок 2.2.1

 

Многоугольник OABCD– область допустимых решений.

Построим прямую уровня

Возьмем из области допустимых решений произвольную точку М(20; 20), подставим в целевую функцию:

 

Z: 40 *20 + 30 * 20 = 1400

40x1 + 30x2 = 1400 – уравнение прямой уровня.

 

Результаты расчётов приведены на рис. 2.2.1.

Определим направление перемещения прямой уровня

α (40; 30) – координаты вектора, в направлении которого нужно перемещать прямую уровня до пересечения с последней граничной точкой области допустимых решений.

Эта точка С.

Найдём её координаты:

 

 

Найдем максимальную прибыль

40*54+30*24=2880

 

Ответ: Для достижения максимальной прибыли 2880 ден.ед. следует производить 54 ед. продукции вида А1 и 24. продукции вида А2.

 

2.3 Решение задачи планирования производства симплекс-методом

 

Введем базисные переменные и преобразуем исходную задачу к виду:

Z= 40x1 + 30x2 + 0x3 + 0x4 + 0x5 → max

 

Решим систему уравнений относительно базисных переменных: x3, x4, x5.

Полагая, что свободные переменные равны 0, получим первый опорный план:

 

X1 = (0,0,240,180,251)

 

Таблица 2.3.1

Итерация № 0

Базис	Сб	X1	X2	X3	X4	X5	Свободные члены	Отношение
X3	0	4	1	1	0	0	240	240/4
X4	0	2	3	0	1	0	180	180/2
X5	0	1	5	0	0	1	251	251/1
Z		-40	-30	0	0	0	0	-

 

При составлении исходной симплекс таблицы (Табл. 2.3.1), коэффициенты при переменных функции ** записываются с противоположными знаками, а свободный член со своим знаком.

Сб – вектор, составленный из координат соответствующих базисных переменных.

Текущий план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Ведущий столбец X1, так как -40 – наименьшее отрицательное число.

За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим.

Таблица 2.3.2

Разрешающий элемент 4

Базис	Сб	X1	X2	X3	X4	X5		Отношение
X3	0	4	1/4	1/4	0	0	60	60
X4	0	2	3	0	1	0	180	90
X5	0	1	5	0	0	1	251	251
Z		-40	-30	0	0	0	0	-

 

От элементов строки 2 отнимаем соответствующие элементы строки 1, умноженные на 2.

От элементов строки 3 отнимаем соответствующие элементы строки 1, умноженные на 1.

От элементов строки ** отнимаем соответствующие элементы строки 1, умноженные на -40 (Табл. 2.3.2)

Заменяем базисную переменную X3 на X1

 

Таблица 2.3.3

Итерация № 1

Базис	Сб	X1	X2	X3	X4	X5	Свободные члены	Отношение
X1	0	1	0,25	0,25	0	0	60	240
X4	0	0	2,5	-0,5	1	0	60	24
X5	40	0	4,75	-0,25	0	1	191	40,21
Z		0	-20	10	0	0	2400	0

 

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты (Табл. 2.3.3).

За ведущий выберем столбец 2, так как -20 наименьший элемент в ** строке.

За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим.

Разрешающий элемент 2,5

Разделим элементы строки 2 на 2,5(Табл. 2.3.3).

 

Таблица 2.3.4

Базис	Сб	X1	X2	X3	X4	X5	Свободные члены	Отношение
X1	0	1	0,25	0,25	0	0	60	240
X4	20	0	1	-0,2	0,4	0	24	24
X5	40	0	4,75	-0,25	0	1	191	40,21
Z		0	-20	10	0	0	2400	0

 

От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на 0,25.

От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на 4,75.

От элементов строки ** отнимаем соответствующие элементы строки 2, умноженные на -20

 

Таблица 2.3.5

Базис	Сб	X1	X2	X3	X4	X5	Свободные члены
X1	0	1	0	0,3	-0,1	0	54
X2	20	0	1	-0,2	0,4	0	24
X5	40	0	0	0,7	-1,9	1	77
Z		0	0	6	8	0	2880

 

X2 = (54, 24, 77, 0, 0)

**(X2) = 40*54 + 30*24 = 2880 (Табл. 2.3.5).

 

Ответ: Для достижения максимальной прибыли 2880 ден.ед. следует производить 54 ед. продукции вида А1 и 24 ед. продукции вида А2. (ответ совпадает с ответом полученным графическим способом).

 

 

2.4 Решение задачи планирования производства с помощью табличного процессора MS Excel

 

1. Ввод данных

Вводим данные таблицы 3 в ячейки EXCEL (рис. 2.4.1.).

• В ячейках B3: С5 введены виды продукции.
• В ячейках B6: C6 находится прибыль от реализации единицы изделия A1 и А2.
• В ячейках D3: D5 находятся ограничения по сырью.

2. Записываем формулы для вычисления ограничений

Введем формулы в ячейки B7: B9

• B7: =B10*B3+B11*C3
• B8: =B10*B4+B11*C4
• B9: =B10*B5+B11*C5

3. Записываем формулу для вычисления целевой функции

Целевая функция находится в ячейке E2

• В ячейку E2 введем формулу: =B10*B6+B11*C6

 

Рисунок 2.4.1

 

4. Заполнение окна процедуры «Поиск решения»

• Целевая функция: E2 ($E$2);

• Вид поиска: max;
• Изменяемые ячейки: B10: B11 ($B$10:$B$11);
• В поле «Ограничения» добавим заданные ограничения:

 

$B$10:$B$11 = целое;

$B$10:$B$11 >= 0;

$B$7 <= $D$3

$B$8 <= $D$4

$B$9 <= $D$5

 

• В окне «Параметры» установить «Линейная модель». Результаты заполнения окна показаны на (рис.2.4.2), (рис. 2.4.3).

 

Рисунок 2.4.2

 

Рисунок 2.4.3

5. Выполнив процедуру «Поиск решения» получим следующие результаты (рис. 2.4.4):

 

Рисунок 2.4.4

 

Ответ: Для достижения максимальной прибыли 2880 ден.ед. следует производить 54 ед. продукции вида А1 и 24 ед. продукции вида А2. (ответ совпадает с ответом полученным графическим способом и соответствует решению задачи симплекс-методом).

 

2.5 Составление математической модели транспортной задачи

 

Задача На три базы А1, А2, А3 поступил однородный груз в количествах: а1, a2, а3 соответственно. Груз требуется развести в пять пунктов: b1 в пункт В1, b2в пункт В3, b3 в пункт В3, b4 в пункт В4, b5 в пункт В5.

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Математическая модель транспортной задачи: