2. Постановка задачи выбора оптимального плана трелевки

Определение цели: необходимо определить такие объемы трелевки с каждой из лесосек на каждый погрузочный пункт, при которых суммарные затраты на трелевку были бы минимальны.

Формулировка проблемы:

Этапы формулировки проблемы включают в себя:

1) управляемые переменные – сменные объемы трелевки с каждой лесосеки на каждый погрузочный пункт, м³;

2) переменные состояния – технологические и технико-экономические факторы (сменные объемы трелевки с каждой лесосеки, вместимость каждого погрузочного пункта, себестоимость трелевки 1 м³ с каждой лесосеки на каждый погрузочный пункт, количество лесосек и погрузочных пунктов);

3) размерность задачи – определяется количеством управляемых переменных и ограничений, с учетом несбалансированности, равняется девяти; временной интервал моделирования – смена;

4) критерий – суммарные затраты на трелевку, р.

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

1) обозначение переменных (объемов трелевки с каждой лесосеки в каждый погрузочный пункт) - x₁₁, x₁₂, x₁₃, x₂₁, x₂₂, x₂₃, (в обозначениях первый индекс соответствует номеру лесосеки, второй – номеру погрузочного пункта).

2)Целевая функция имеет следующий вид:

y= =8,8x₁₁+0,6x₁₂+1,3x₁₃+2x₂₁+2,5x₂₂+0,3x₂₃

3) построение ограничений производится на основе содержания задачи, где суммарный объем трелевки в смену Q=Q₁+Q₂ =300м³, а вместимость погрузочных пунктов V=V₁+V₂+V₃=350 м³. В этом случае имеем несбалансированную транспортную модель (Q<V). Приведение транспортной модели к сбалансированной (с целью того, чтобы избыток транспортируемой древесины в 50 м³ оптимально распределялся между лесосеками) осуществляется введением дополнительного фиктивной лесосеки Q_4ф с вместимостью 50 м³. В связи с тем, что реально такой лесосеки нет(трелевка на нее не производится), считаем, что себестоимость трелевки равняется 0. При этом появляются три дополнительные переменные x₃₁, x₃₂, x₃₃ и ограничения примут следующий вид:

x₁₁+x₁₂+x₁₃ =Q₁, x₁₁+x₂₁+x₃₁ =V₁

x₂₁+x₂₂+x₂₃ =Q₂, x₁₂+x₂₂+x₃₂ =V₂

x₃₁+x₃₂+x₃₃ =Q_3ф, x₁₃+x₂₃+x₃₃ =V₃

3. Алгебраическое решение задачи методом потенциалов

Алгебраическое решение поставленной задачи

В связи с тем, что модель была предварительно сбалансирована (Q=V), то отсюда следует, что одно уравнение является зависимым и транспортная модель содержит m+n-1 (3+4-1)=6 независимых уравнений и начальное базисное допустимое решение должно иметь 6 базисных переменных.

Для нахождения начального базисного допустимого решения используем процедуру, основанную на правиле северо-западного угла.

Начальное решение:

	V1	V2	V3	∑Q
Q1	^8^,^8 100	^0,^6	^1^,^3	100
Q2	^2 0	^2^,^5 200	^0,3	200
Q3ф	^0	^0 0	^0 50	50
∑V	100	200	50

Базисные переменные принимают значения: x₁₁=100, x₂₂=200, х₃₃=50, остальные небазисные переменные равняются 0. Для полученного плана затраты на трелевку составят:

у = 8,8*100 + 2,5*200 = 1380 у.е. в смену.

Оптимален ли этот план? На этот вопрос дает ответ условие оптимальности симплекс-метода (наличие положительных коэффициентов при небазисных переменных транспортной таблицы).

Первая итерация:

1. Нахождение вводимой в базис переменной (метод потенциалов):

x₁₁=u₁+v₁=C₁₁=8,8

x₂₁=u₂+v₁=C₂₁=2

x₂₂=u₂+v₂=C₂₂=2,5

x₃₂=u₂+v₃=C₂₃=0

x₃₃=u₃+v₁=C₃₁=0

Полагаем, что u₁=0, тогда: v₁=8,8, v₂=9,3, u₂=-6,8 v₃= 9,3, u₃= -9,3,.

Оценки потенциалов небазисных переменных: x₁₂ : C₁₂= 0+9,3-0,6 = 8,7

x₁₃ : C₁₃= 9,3-1,3 = 8

x₂₃: C₂₃= -6,8+9,3-0,3 = 2,2

x₃₁: C₃₁= -9,3+8,8-0 = -0,5

Небазисная переменная x₁₂, имеющая максимальную положительную оценку С₂₁, выбирается в качестве вводимой в базис.

2. Нахождение переменной, выводимой из базиса. Последовательность обхода следующая:

	V1	V2	V3	∑Q
Q1	^8^,^8 100 -	^0,^6 Х12 +	^1^,^3	100
Q2	^2 0+	^2^,^5 200 -	^0,3	200
Q3ф	^0	^0 0	^0 50	50
∑V	100	200	50

_{Выводим из базиса x11=100, тогда значение х12=100 и транспортная задача имеет вид:}

	V1	V2	V3	∑Q
Q1	^8^,^8	^0,^6 100	^1^,^3	170
Q2	^2 100	^2^,^5 100	^0,3	180
Q3	^0,5	^0,7 0	^0,9 50	130
∑V	100	200	50

Для полученного плана затраты на трелевку составят:

у = 0,6*100 + 100*2 + 2,5*100= 260 у.е. в смену.

Оптимальность нового решения определяется вычислением новых потенциалов:

x₁₂=u₁+v₂=C₁₂=0,6

x₂₁=u₂+v₁=C₂₁=2

x₂₂=u₂+v₂=C₂₂=2,5

x₃₂=u₃+v₂=C₃₂=0

x₃₃=u₃+v₃=C₃₃=0

Полагаем, что u₁=0, тогда: v₃=0,6 v₂=0,6, u₂=1,9, u₃= -0,6, , v₁= 0,1.

Оценки потенциалов небазисных переменных:

x₁₃: C₁₃= -0,7

x₂₃: C₂₃= 0

x₃₁: C₃₁= -0,6

x₁₁: C₁₁= -8,7

Небазисная переменная x₂₃, имеющая максимальную положительную оценку С₂₃, выбирается в качестве вводимой в базис.

3. Нахождение переменной, выводимой из базиса. Последовательность обхода следующая: x₃₂ – x₂₂ – x₂₄ – x₃₄ – х₃₂.

	V1	V2	V3	∑Q
Q1	^8^,^8	^0,^6 100	^1^,^3	100
Q2	^2 100	^2^,^5 100 -	^0,3 Х23+	200
Q3	^0,5	^0,7 0+	^0,9 -50	50
∑V	100	200	50

Выводим из базиса x₂₂=50, тогда значение х₃₂=50 и транспортная задача имеет вид:

	V1	V2	V3	∑Q
Q1	^8^,^8	^0,^6 100	^1^,^3	100
Q2	^2 100	^2^,^5 50 -	^0,3 50	200
Q3	^0,5	^0,7 50+	^0,9 0	50
∑V	100	200	50

Для полученного плана затраты на трелевку составят:

y = 50*0,7+50*2,5+50*0,3=175y.e. в смену

Оптимальность нового решения определяется вычислением новых потенциалов:

x₁₂=u₁+v₂=C₁₂=0.6

x₂₁=u₂+v₁=C₂₁=2

x₂₂=u₂+v₂=C₂₂=2,5

x₂₃=u₂+v₃=C₂₃=0,3

x₃₂=u₃+v₂=C₃₂=0

Полагаем, что u₁=0, тогда: v₂=0,6 v₁=0,1 u₂=1,9 u₃=-0,6 v₃=-1,6.

Оценки потенциалов небазисных переменных:

x₁₁: C₁₁= -8,7

x₁₃: C₁₃=-2,9

x₃₁: C₃₁= -0,5

x₃₃: C₃₃= -2,2

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