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

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

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

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

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

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

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

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

Пример: Управление механизации имеет 3 бульдозера с известным годовым фондом времени. К строительству предложены три объекта с большим объемом работ и известной прибылью по объектам за единицу объема работ. Необходимо выбрать виды и объемы работ по объектам на планируемый год, при выполнении которых управление получит максимальную прибыль.

Матрица исходных данных

Таблица 21

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

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

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

,

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

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

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

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

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

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

Таблица 22

Базисные переменные	Свободные члены в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

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

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

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

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

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

Коэффициент, который находится на пересечении столбца вводимой переменной Х₃ и строки выводимой переменной X₆, и называется разрешающим элементом (4);

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

Таблица 23

Базисные переменные	Свободный член в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

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

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

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

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

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

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

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

Таблица 24

Базисные переменные	Свободные члены в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

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

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

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

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

Т = 2×11,2 + 4×0 + 1×8,2 = 22,4 + 8,2 = 30,6;

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

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

Т = 3×11,2 + 5×0 +2×8,2 = 33,6 +16,4 = 50;

Х₅ = 0.

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.

Задачи для самостоятельного решения