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

Лекция №

Постановка задачи и выбор критерия оптимизации. Пусть управле­ние механизации имеет заказы на выполнение определенных видов работ Pj. Известны необходимые машины или комплекты машин М₁, М2 и М₃, время аij выполнения у-го вида работ i- мкомплектом машин, фонд времени b_i по каждому i -му комплекту машин и какая прибыль С i. может бытьполу­чена при выполнении единицы работы каждого j -го вида (таблица 8.1).

Таблица 8.1

 

 

 

 

Комплекты машин Mi	Виды работ Рj	Фонд времени bj
Pi	Р2	Рз	Р4
Время aij выполнения единицы работы Рj
М1	a11= 3	a12=5	a13 = 2	a14 = 7	b1 = 15
М2	a21 = 4	a22 = 3	a23 =3	а24 = 5	b2 = 9
М3	a31 = 5	а32 = 6	а зз = 4	а34 = 8	b3 = 30
Прибыль	С 1 = 40	С2= 50	С3 =30	C4 = 20

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

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

3 Х₁ + 5 Х₂ + 2 Х ₃ + 7 Х ₄ < 15,

4 Х ₁ + 3 Х₂ +3 Х ₃+5х₄ <9,

5 Х ₁ + 6 Х₂ +4 Х ₃ +8 Х ₄ <30.

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

a₁₅ = 1, a₂₅ = 0, a₃₅ = 0, a₁₆ ⁼ 0, a₂₆ ⁼ 1, a₃₆ ⁼ 0, a₁₇ ⁼ 0, a₂₇ ⁼ 0, a₃₇ ⁼ 1.

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

3х₁, + 5х₂ + 2х₃ + 7х₄ +1х₅ + 0х₆ + 0х₇ = 15

4х₁+3х₂ +3х₃ +5х₄ +0х₅ +1х₆ +0х₇ =9,

5х₁ +6х₂ +4х₃ +8х₄ +0х₅ +0х₆ +1х₇ =30.

Кроме того, следует ввести дополнительные ограничения, исходя из ре-альности задачи. Все искомые переменные задачи могут быть равны или больше нуля.

Критерий оптимизации — суммарная прибыль, получаемая управлени­ем механизации от выполнения тех или иных работ, может быть представ­лено в таком виде

 

y=C₁ x₁ +_… + C_j x_j +… + C₇ x₇ = C_j x_j

 

Прибыль, получаемая от выполнения фиктивных объемов работ, принимается равной нулю: С₅ = 0, С ₆ = 0, С₇ = 0.

По форме, построенная модель это модель общей линейной распреде-лительной задачи.

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

Исследование математической модели. Решение общей линейной распределительной задачи, так же как и транспортной, как правило, разби­вается на два этапа. На первом этапе находят какое-нибудь решение, удов­летворяющее совокупности линейных равенств и ограничениям, или убеж­даются в том, что такого решения не существует. Этот этап называется отысканием опорного (начального) плана (базиса). На втором этапе произ-

водится последовательное улучшение плана (базиса). В некоторых распре-
делительных задачах базис просматривается непосредственно, а во многих
его необходимо найти.

В рассматриваемой задаче базис легко определяется. Для этого необхо­димо взять какие-либо т неизвестных, желательно наиболее редко встре- чающихся в системе уравнении и выразить их через остальные неизвест- ные. В нашей системе уравнений (т = 3) это x₅, x₆, х₇ , которые и выражаем через оставшиеся неизвестные х₁, х₂, х₃, х₄.

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

 

 

 

х5 = 15 -

(3х₁ + 5х₂ +2 х₂ + 7х₄),

Х₆ =9 - (4х₁ + 3х₂ +3х₃ + 5х₄),

х₇ =30 - (5х₁+6х₂+4х₃+8х₄).

Переменные, находящиеся в левой части системы уравнений, называ- ются базисными (основными), а в правой части — небазисными (неоснов­ными). Для определения значений базисных переменных x₅, x₆, х₇ необхо-димо приравнять к нулю небазисные переменные x₁, x₂, х₃, x_4. Полученное таким образом решение называется базисным (0, 0, 0, 0, 15, 9, 30). После этого переходят ко второму этапу решения задачи.

Для решения общей линейной распределительной задачи на втором этапе существует несколько методов; ограничимся рассмотрением одного из них, который в настоящее время имеет наибольшее распространение, это симплекс-метод (см. гл. III, § 3.2).

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

Решение задачи сводится к последовательному составлению симплекс^
таблиц (табл. 8.2).;

 

 

 

Базисные переменные	Свободные члены	ЖоэффиццеБйы црияебазисньк и базисных переменных хг
Х\		■ Ъ	х4	х5	х6	х7
xs* Хб х7	15 9 30	3 4	3 • 6	2 3 4	5. 8	1 0 0		0 0
Целевая функцияу					.20	щ

Работа с симплекс-таблицей полностью соответствует ранее изложен­
ному алгоритму. После заполнения исходной симплекс-таблшш начинается
подготовка к составлению второй. Для этого йспользу^етса рйнее изложен­
ный алгоритм симплеке-метеща: v

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

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

I 4) определяем, какая из базисных переменных должна быть выведена Ш?базиса. Для этого определяем минимальное частное от деления соответ­ствующих свободных членов и положительных коэффициентов столбца, отмеченного звездочкой (3, 3, 5). Базисная переменная х₅, соответствующая минимальному частному, должна быть выведена из базиса. При наличии ^нескольких минимальных частных выбирается одна из базисных перемен-|ных. Эту строку отметим звездочкой.

■[:■■■:

1 Коэффициент, который находится на пересечении столбца вводимой в
| базис переменной, (х₂) и строки выводимой из базиса переменной (х₅), назы-
»вается разрешающим элементом. В нашем примере это число 5;
щ 5) вводимую в базис переменную х₂ выразим через переменную, выводи­
мую из базиса х₅, и небазисные переменные\x_h x₃, х₄. Для этого составляем
^вторую симплекс-таблицу (табл. 8.3).
Ш ■--:,• ^;'.■--:-..::,.... '■.,;;:..,■,.....;,:;-.. -...Таблица8.3

 

 

( Базисные -: леремен- ;v:":- -.ные'.у- ■■ "	Сво­бодные члены	Коэффициенты при небазисных и базисных \.Х\ перемённыхх/
	;. х2	XI*			х6
1 х2 |.. X-i; :	3: -:■: в	3/5 11/5 7/5	1 0 0	2/5 9/5 8/5	7/5 4/5 -2/5	№ -3/5 -6/5	0 1 0	0 0
Целевая функция у	-150				-50	-10

г В ней базис выражается переменными х_ъ х₆, х-,. Делим строку преды­дущей таблицы (см. табл. 8. 2), отмеченную звездочкой (соответствующая выводимой переменной), на разрешающий элемент - число 5 и результат записываем в новую таблицу (первая строка табл. 8.3);

6) все остальные базисные переменные Хб, Xj и целевую функцию выра­жаем через новые небазисные переменные x_h x₃, jc₄ и х₅. Для этого подучен­ная строка в новой таблице х₂ умножается на такое число, чтобы после сло­жения с преобразуемой строкой первой таблицы (см. табл. 8.2) в столбце х₂ (см. табл. 8.3) появился ноль.

В соответствии со сказанным, для получения коэффшшеегов второй табл. 8.3 умножаем коэффидиеш.ы строяи х₂ табх 83 на —3 i

дываем их с соответствующими коэффициентами второй строки табл. 8.2. Аналогично определяем коэффициенты для третьей строки.

После заполнения табл. 8.3 расчет повторяется с п. 1: ■■■?Ш

1) выясняем — решение не оптимально, так как в последней строке i
второй таблицы есть положительные коэффициенты (см, табл. 83);

2) решение есть; - ^ .,<^::,

3) в качестве вводимой в базис небазисной переменной берем х_ъ (или
xj), как имеющей наибольший положительный коэффициент. Отмечаем
столбец х₃ звездочкой (см. табл. 8.3);

4) в качестве выводимой из базиса переменной берем х₆, так как для
нее частное от деления свободного члена на коэффициент при л:₃ мини­
мально (0). Разрешающий множитель равен 9/5;

5) рассчитываем симплекс-таблицу (табл. 8.4), которая получается
аналогично табл. 8.3.

Таблица 8.4

 

 

Базисные перемен­ные	Свободные члены	Коэффициенты при небазисных и базисных переменных х,-
х\	х2	X)	. х4		х6	х7:
Х2 х3 Ху	3 0 12	1/9 11/5 -5/9	1 ' 0 0	0 1 0	11/9 4/9 -10/9	1/3 -3/9 -2/3	-2/9 5/9 -8/9	0 0
Целевая функция у	-150	-20/9			-490/9	-20/3	-50/9

В ней последняя строка не содержит положительных коэффициентов и, следовательно, находим оптимальное базисное решение, максимизирующее критерий оптимизации (прибыль). Базисное, которое будет равно:

х₂ =3, х₃ = 0, х₄ = 0, х₇ =12, *, =0, х₅ = 0, х₆ =0.

Таким образом, если управление механизации будет выполнять работь! вида Рг ^в объеме Х2 — 3, а остальные виды работ не будет выполнять, то оно обеспечит себе максимальную прибыль; При этом фонд времени комплек­тов машин будет использован для:

первого комплекта — полностью

^Т3 =^32*2 =6*3 = 18, Ь₃=30

второго комплекта — полностью

Т₂ =а₂₂х₂ =3*3 = 9,

Л =9

третьего комплекта — не полностью

Т_ъ =а₃₂х₂ =6*3 = 18, Ь₃ =30 '..'_'■

Максимальная прибыль, которая будет получена управлением механи­зации, составит:

у - 40*0 + 50*3 + 30*0 + 20*0 =150.

 

Если некоторые переменные ограничены снизу

Xj<dj,{j= 1,2.... 7),

то для учета ограничений достаточно сделать замену переменных

I Если в качестве критерия оптимизации используются приведенные |з&траты, то для использования рассмотренного алгоритма вводится замена

у' - -у. Для оперативного решения рассмотренной задачи целесообразно

использовать ЭВМ (см. гл. 3.2).