4. Область оптимального использования средств механизации

В процессе планирования и выбора видов и объемов работ под существующий парк машин на следующий год (планируемый период) возникает необходимость расчета и анализа видов и объемов работ с целью получения максимальной прибыли при их выполнении. Для решения поставленной задачи необходимы исходные данные:

Ai – марки машин или комплекты;

Вj – виды работ на объектах;

Аij – время выполнения единицы объема работ i-й машиной на j-м объекте;

Сj – прибыль при выполнении единицы объема работ на объектах;

Пгi – годовой фонд времени работы машин.

В процессе решения таких задач определяются виды работ и их объемы на планируемый период с получением максимальной прибыли при их выполнении.

Пример решения задачи

Условие задачи. Управление механизации имеет 3 бульдозера (ДЗ-104; ДЗ-110А; ДЗ-10) с известным годовым фондом времени (Пгi).

К строительству предложены три объекта (B₁ – В₃) с большим объемом работ и известной прибылью по объектам за единицу объема работ (Сij).

Необходимо выбрать виды и объемы работ по объектам на планируемый год, при выполнении которых управление получит максимальную прибыль.

Матрица исходных данных представлена в табл. 4.1.

Таблица 4.1

Mapки бульдозеров	Время аij на выполнение ед. объема работ по объектам Вj			Годовой фонд времени Пгi, ч
	В1	В2	Вз
ДЗ-104	2	4	1	40
ДЗ-110А	3	5	2	50
ДЗ-10	1	3	4	44
Прибыль Сij за ед. объема работ, руб.	20	10	30	-

Зная фонд времени работы каждого комплекта машин, можно записать следующую систему неравенств:

2X₁ + 4Х₂+ 1X₃ ≤ 40;

3Х₁ + 5Х₂ + 2Х₃ ≤ 50;

1X₁ + 3Х₂ + 4Х₃ ≤ 44.

Для упрощения решения целесообразно преобразовать систему неравенств в систему равенств, введя фиктивные виды работ Х₅, Х₆, Х₇, которые равны неиспользованному фонду времени по каждой машине. При этом время выполнения фиктивной работы каждой машиной принимается равным:

а_1.4 = 1 а_2.4 = 0 а_3.4 = 0

а_1.5 = 0 а_2.5 = 1 а_3.5 = 0

а_1.6 = 0 а_2.6 = 0 а_3.6 = 1

Тогда система равенств запишется так:

2Х₁ + 4Х₂ + 1X₃ + 1X₄ + 0Х₅ + 0X₆ = 40,

3X₁ + 5Х₂ + 2Х₃ + 0Х₄ + 1Х₅ + 0Х₆ = 50,

1Х₁ + 3X₂ + 4X₃ + 0Х₄ + 0Х₅ + 1Х₆ = 44.

Для решения системы уравнений принимается дополнительное ограничение: все искомые переменные задачи могут быть равны или больше нуля.

Критерий оптимизации – максимальная суммарная прибыль, получаемая управлением механизации от выполнения тех или иных работ на объектах:

max

Таким образом, задача свелась к оптимальному распределению предлагаемых объемов работ для имеющихся машин с использованием их годового фонда времени и получения максимальной прибыли.

Для перехода к решению задачи запишем систему уравнений в следующем виде:

Х₄ = 40 - (2X₁ + 4Х₂ + Х₃),

Х₅ = 50 - (3X₁ + 5X₂ + 2X₃),

X₆ = 44 - ( X₁ + 3X₂ + 4X₃).

Переменные, находящиеся в левой части системы уравнений, называются базисными (основными), а в правой части – небазисными (не основными). Для решения распределительной задачи наиболее подходит симплекс-метод. Решение сводится к последовательному составлению симплекс-таблицы (табл. 4.2).

После заполнения исходной симплекс-таблицы начинается подготовка к составлению следующей, для этого:

1) проверяем базисное решение на оптимальность. Просматриваем знаки коэффициентов целевой функции Y (последняя строка таблицы), кроме коэффициентов при свободном члене. Положительные коэффициенты в последней строке говорят о том, что исходное решение еще не оптимально.

Таблица 4.2

Базисные переменные	Свободные члены вi	Коэффициенты аij и Cj при небазисных и базисных переменных
		Х1	Х2	Х3*	Х4	Х5	Х6
Х4	40 (40)	2	4	1	1	0	0
Х5	50 (25)	3	5	2	0	1	0
Х6*	44 (11)	1	3	4	0	0	1
Целевая функция Y	0	20	10	30	0	0	0

2) проверяем задачу на наличие решения. Так как над всеми положительными коэффициентами целевой функции нет ни одного столбца с неположительными числами, то значит, задача имеет решение;

3) выбираем из небазисных переменных ту, которая способна при введении ее в базис увеличить значение целевой функции, т.е. переменную, имеющую наибольший положительный коэффициент в последней строке, и отмечаем её звездочкой, в нашей задаче Х₃;

4) определяем, какая из базисных переменных должна быть выведена из базиса. Для этого определяем минимальное частное от деления соответствующих свободных членов и положительных коэффициентов столбца, отмеченного звездочкой (1, 2, 4). Базисная переменная Х₆, соответствующая минимальному частному, должна быть выведена из базиса. Эту строку отметим звездочкой. Коэффициент, который находится на пересечении столбца вводимой переменной Х₃ и строки, выводимой переменной X₆, и называется разрешающим элементом (4);

5) вводимую в базис переменную Х₃ выразим через переменную, выводимую из базиса Х_6, и небазисные переменные X₁, Х₂. Для этого составляем следующую симплекс-таблицу (табл. 4.3). В ней базис выражается переменными Х₄ Х₅ Х₃. Делим строку предыдущей таблицы, отмеченную звездочкой на разрешающий элемент (4), и результат записываем в табл.4.3 (третья строка);

6) все остальные базисные переменные Х₄ и X₅ и целевую функцию выражаем через новые небазисные переменные Х₁ Х₃. Для этого полученная строка в новой таблице (табл. 4.3) Х₃ умножается на такое число, чтобы после сложения с преобразуемой строкой табл. 4.2 в столбце Х₃ появился ноль.

Таблица 4.3

Базисные переменные	Свободный член вi	Коэффициенты аij и Cj при небазисных и базисных переменных
		Х1*	Х2	Х3	Х4	Х5	Х6
Х4	29 (16,5)	7/4	13/4	0	1	0	- 1/4
Х5*	28 (11,2)	10/4	14/4	0	0	1	- 1/2
Х3	11 (44)	1/4	3/4	1	0	0	1/4
Целевая функция	-330	50/4	-50/4	0	0	0	- 30/4

В соответствии со сказанным для строки Х₄ - (–1); для строки X₅ - (-2), для целевой функции – (-30). После заполнения табл. 4.3 расчет повторяется с пункта 1.

1. Выясняем: решение не оптимально, так как в последней строке табл.4.3 есть положительный коэффициент - (50/4).

2. Решение есть.

3. В качестве вводимой в базис небазисной переменной берем Х₁ как имеющей наибольший положительный коэффициент - 50/4. Отмечаем столбец X₁ звездочкой.

4. В качестве выводимой из базиса переменной берем Х₅, так как для нее частное от деления свободного члена на коэффициент минимально (11,2). Разрешающий множитель равен 10/4.

Рассчитываем симплекс-таблицу.4.4, которая получается аналогично табл. 4.3.

Таблица 4.4

Базисные переменные	Свободные члены вi	Коэффициенты аij и Сj при небазисных и базисных переменных
		Х1	Х2	Х3	Х4	Х5	Х6
Х4	9,4	0	-33/20	0	I	-7/10.	1/10
Х1	11,2	1	14/10	0	0	4/10	-2/10
Х3	8,20	0	4/10	1	0	-1/10	3/10
Целевая функция	-470	0	-30	0	0	-5	-5

В полученной табл. 4.4 решение оптимально. В нашем случае

Х₁= 11,2; Х₂ = 0; Х₃ =8,2; Х₄ = 9,4; Х₅=0; Х₆=0.

Таким образом, если управление механизации будет выполнять работы вида В₁ в объеме X₁ = 12,2 и В₃ в объёме Х₃ = 8,2, то оно обеспечит себе максимальную прибыль. При этом фонд времени будет использован:

1-ой машиной:

Пг1 = 2×11,2 + 4×0 + 1×8,2 = 22,4 + 8,2 = 30,6.

Недостающий фонд времени (простой) Х₄ = 9,4;

2-ой машиной:

Пг2 = 3×11,2 + 5×0 +2×8,2 = 33,6 +16,4 = 50.

Недостающий фонд времени (простой) Х₅ = 0;

3-й машиной:

Пг3 = 1×11,2 + 3×0+ 4×8,2 = 11,2 + 32,8 = 44.

Недостающий фонд времени (простой) Х₆ = 0.

Максимальная прибыль

Y = 11,2×20 + 0×10 + 8,2×30 = 224 + 246 = 470.