Стандартная форма линейных оптимизационных моделей 6 страница

Столбец 2 и строка 2 одновременно приводят к выполнению соответст. ограничений. Если вычеркивается столбец 2, то на следующем шаге переменная х₂₃ становится базисной с нулевым значением, поскольку величина предложения в строке 2 равна 0. (табл.3).

Если вычерчивается строка 2, то х₃₂ становится нулевой базисной переменной.

Начальные решения в табл. 2 и 3 содержат необходимое количество базисных переменных, равное m + n – 1 = 6. Использование правила северо-западного угла всегда приводит к нужному числу базисных переменных.

Нахождение вводимой в базис переменной

(метод потенциалов).

Вводимую в базис переменную находят, используя условия оптимальности СМ. Вычисление коэффициентов целевой функции основано на соотношениях между прямой и двойственной з-ми. Сначала рассмотрим, как реализуется метод, а затем дадим строгое объяснение вычислительных процедур на основе теории двойственности. Для определения вводимой в базис переменной можно использовать и другой метод, называемый методом «опорных элементов». Хотя вычислительные процедуры в рамках этих методов полностью эквивалентны, метод опорных элементов кажется совершенно непохожим на СМ.

В методе потенциалов строке i и столбцу j транспортные таблицы ставятся в соответствии числа U_i и V_j. Для каждой базисной переменной Х_ij текущего решения потенциалы U_i и V_j должны удовлетворять уравнению

U_i + V_j = C_ij

Эти уравнения приводят к системе, состоящей из m + n – 1 уравнений (поскольку всего имеется m + n – 1 базисных переменных), в которых фигурируют m + n неизвестных. Значения потенциалов можно определить из этой системы, придавая одному из них произвольное значение (обычно U₁ полагается равным нулю) и затем решая систему из m + n – 1 уравнений относительно m + n – 1 остальных потенциалов. Как только решение получено, оценки для небазисных переменных Х_pg определяются в соответствии с соотношением

С_pq = U_p + V_q – C_pq.

(эти величины не зависят от выбора значения U₁ ). После этого для включения в базис выбирается небазисная переменная, имеющая самую большую положительную оценку C_pq (сравните с условием оптимальности СМ при решении задачи на отыскание минимума).

Если эту процедуру применить к небазисным переменным табл. 2 (текущее решение), то уравн1ения, связанные с базисными переменными, будут иметь вид:

X₁₁ : U₁ + V₁ = C₁₁ = 10; U₁ = 0; V₁ = 10

X₁₂: U₁ + V₂ = C₁₂ = 0; U₁ = 0; V₂ = 0

X₂₂: U₂ + V₂ = C₂₂ = 7; V₂ = 0; U₂ = 7

X₂₃: U₂ + V₃ = C₂₃ = 9; U₂ = 7; V₃ = 9 – 7 = 2

X₂₄: U₂ + V₄ = C₂₄ = 20; U₂ = 7; V₄ = 20 – 7 = 13

X₃₄: U₃ + V₄ = C₃₄ = 18; V₄ = 13; U₃ = 18 – 13 = 5

Полагая U₁ = 0, получим значения потенциалов V₁ = 10; V₂ = 0; V₃ = 9 –7 = 2; V₄ = 20 – 7 = 13; U₃ = 18 – 13 = 5. Оценки для небазисных переменных определяется следующим образом:

X₁₃ : C₁₃ = U₁ + V₃ – C₁₃ = 0 + 2 – 20 = -18

X₁₄ : C₁₄ = U₁ + V4 – C₁₄ = 0 + 13 – 11 = 2

X₂₁ : C₂₁ = U₂ + V₁ – C₂₁ = 7 + 10 – 12 = 5

X₃₁ : C₃₁ = U₃ + V₁ – C₃₁ = 5 + 10 – 0 = 15

X₃₂ : C₃₂ = U₃ + V₂ – C₃₂ = 5 + 0 – 14 = -9

X₃₃ : C₃₃ = U₃ + V₃ – C₃₃ = 5 + 2 – 16 = -9

Поскольку переменная Х₃₁ имеет максимальный положительный оценку С_pq, она и выбирается в качестве вводимой в базис.

Уравнения U_i + V_j = C_ij, используемые для нахождения потенциалов, имеют настолько простую структуру, что на самом деле их нужно записывать в явном виде. Обычно гораздо проще определить потенциалы непосредственно из транспортной таблицы, заметив, что U_i строки i и V_j столбца j прибавляются к C_ij, если на пересечении строки i и столбца j находится базисная переменная X_ij. Определив U_i и V_j можно вычислить C_pq для всех небазисных переменных X_pq, прибавляя U_p строки p к V_q столбца q и затем вычитая величину C_pq, стоящую на пересечении строки p и столбца q.

Нахождение переменной, выводимой из базиса

(построение цикла).

Этот шаг эквивалентен использованию условия допустимости в СМ. Вместе с тем, поскольку все коэффициенты в ограничениях транспортной задачи равны либо нулю, либо 1, отношения, используемые при проверке условия допустимости, всегда будут иметь знаменатель, равный 1. Поэтому значения базисных переменных сразу же дают соответствие отношения.

Для определения min отношения построим замкнутый цикл, соответствующий вводимой переменной (Х₃₁ на данной итерации). Цикл начинается и заканчивается выбранной переменной. Он состоит из последовательности горизонтальных и вертикальных (связанных) отрезков, концами которых должны быть базисные переменные (за исключением тех концов, которые относятся к вводимой в базис переменной). Это означает, что каждая ячейка, стоящая на изломе цикла, должна содержать базисную переменную. Табл. 4 иллюстрирует цикл, соответствующий вводимой переменной х₃₁, для базисного решения из табл. 2.

Таблица 4.

	5 10	10 0	20	11
	12	5 7	15 9	5 20
3	Х31 0	14	16	5 18

Этот цикл можно выразить при помощи базисных переменных следующим образом: Х₃₁ ® Х₁₁ ® Х₁₂ ® Х₂₂ ® Х₂₄ ® Х₃₄ ® Х₃₁. Несущественно, в каком направлении (по часовой или против часовой стрелки) происходит обход цикла. Заметим, что для каждого решения и соответствует небазисной переменной можно построить лишь один цикл. Из табл. 4. видно, что если значение Х₃₁ (вводимой в базис переменной) увеличится на единицу, для сохранения допустимости решения значения базисных переменных, стоящих на изломах Х₃₁ цикла, необходимо скорректировать следующим образом: уменьшить Х₁₁ на единицу, увеличить Х₁₂ на единицу, уменьшить Х₂₂ на единицу, ­Х₂₄ на единицу и, наконец, ¯Х₃₄ на единицу. Этот процесс обозначается знаками + и - в соответствии местах таблицы 4. Введенные изменения не нарушают ограничений, накладываемых на объем производства и спрос.

Переменная, выводимая из базиса, выбирается из находящихся на изломах цикла переменных, значения которых уменьшаются при увеличении Х₃₁. Они располагаются в таблице 4. в местах, помеченных знаком -. Из таблицы 4. следует, что Х₁₁, Х₂₂, Х₃₄ – базисные переменные, уменьшающиеся с ростом Х₃₁. Выводимой из базиса переменной становится та, которая имеет наименьшее значение, поскольку именно она раньше всех достигнет нуля, и любое дальнейшее уменьшение делает ее отрицательной (сравните с условием допустимости в СМ, где исключаемая переменная определяется min отношением). В данном примере три - - переменных Х₁₁; Х₂₂ и Х₃₄ имеет одно и то же значение (=5); в этом случае любую из них можно исключить из базиса. Пусть выбрана переменная Х₃₄; тогда значение Х₃₁ становится равным 5, а переменные, находящиеся на изломах цикла (базисные), соответствующим образом корректируются (то есть каждая из них увеличивается или уменьшается на 5 единиц в зависимости от знака + или -) Новое решение приведено в таблице 5. Соответствующая стоимость – 0 * 10 + 15 * 0 + 0 * 7 + 15 * 9 + 10 * 20 + 5 * 0 = 335 дол. Полученная стоимость отключается от стоимости, соответствующему начальному решению (табл. 2.), на 410 – 335 = 75 долл, то есть на величину, приписанную переменной Х₃₁ = (5) и умножаемую на С₃₁ (=5)

Таблица 5.

	0 10	15 0	20	11
	12	0 7	15 9	10 20
	5 0	14	16	18

Базисное решение в таблице 5 вырожденное, поскольку базисные переменные Х₁₁ и Х₂₂ = 0. Однако вырожденность не требует никаких дополнительных мер предосторожности; с нулевыми базисными переменными оперируют точно так же, как с переменными имеющими положительные значения.

Оптимальность нового базисного решения (табл. 5.) проверяется вычислением новых потенциалов (табл.6). Величины С_pq указывается в юго-западном углу каждого небазисного элемента. Таблица 6.

	V1 = 10	V2 = 0	V3 = 2	V4 = 13
U1 = 0	0 10	15 0	20 -18	11 +2
U2 = 7	Х21 12 +5	0 7	15 9	10 20
U3 = -10	5 0	14 -24	16 -24	18 -15

Базисная переменная Х₂₁, имеющая наибольшую положительную оценку C_pq, войдет в решение. Замкнутый цикл, соответствующий Х₂₁, показывает, что переменной, исключаемой из базиса, может быть как Х₁₁, так и Х₂₂. Выберем в качестве такой переменной Х₁₁. В таблице 7 представлено новое базисное решение, полученное из таблицы 6 (Х₂₁ вводится в базис, а Х₁₁ исключается).

Таблица 7.

	V1 = 5	V2 = 0	V3 = 2	V4 = 13
U1 = 0	10 -5	15 0	20 -18	Х14 11 +2
U2 = 7	0 12	0 7	15 9	10 20
U3 = -5	5 0	14 -19	16 -19	-10

Значения U_i; V_j и C_pq вычисляем заново. В таблице 7 переменной, вводимой в базис, и исключаемой переменной является Х₁₄ и Х₂₄ соответственно. Осуществив соответствующие изменения в таблице 7 можно получить новое решение, представленной в таблице 8. Поскольку все С_pq в таблице 8 неположительные, полученные решение оптимально (сравните с условием оптимальности СМ при решение задачи на отыскание минимума.

Таблица 8.

	V1 = 5	V2 = 0	V3 = 2	V4 = 11
U1 = 0	10 -5	15 0	20 -18	Х14 11
U2 = 7	0 12	10 7	15 9	20 -2
U3 = -5	5 0	14 -19	16 -19	-12

Оптимальное решение формулируется следующим образом. Перевезти 5 единиц из пункта производства 1 в пункт потребления 2, заплатив 5 * 0 = 0 долл., 10 единиц из 1 в 4 за 10 * 11 = 110 долл., 15 единиц из 2 в 3 за 15 * 9 = 135 долл. И 5 единиц из 3 в 1 за 5 * 0 = 0 долл. Суммарные транспортные расходы составляют 135 долл.

ЛЕКЦИЯ 13:

Улучшенное начальное решение. Приближенный метод Фогеля (ПМФ).

Метод северо-западного угла, не обязательно дает «хорошее» начальное решение для транспортной задачи. Опишем две процедуры, обеспечивающие получение начального решения путем выбора «дешевых» маршрутов.

Метод наименьшей стоимости.

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

Таблица (1а).

	0 10	15 0	20	0 11
	12	0 7	15 9	10 20
	5 0	14	16	18

В таблице (1а) приведено начальное решение, полученное следующим образом: Х₁₂ и Х₃₁ – переменные, которым соответствуют минимальные стоимости (С₁₂ = С₃₁ = 0). Выберем произвольно Х₁₂. Соответственно значения спроса и объема производства определяют Х₁₂ = 15, то есть и по строке, и по столбцу ограничения выполняются. После вычерчивания столбца 2 объем производства в строке 1 остается равным нулю. Теперь среди оставшихся элементов минимальная стоимость соответствует переменной Х₃₁. Значения Х₃₁ = 5 удовлетворяет ограничениям и по столбцу 1, и по строке 3. После вычеркивания строки 3 оставшийся спрос в столбце 1 = 0. Наименьший невычеркнутый элемент – С₂₃ = 9.

Дата добавления: 2015-06-04