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

Ограничения на спрос и объем производства определяют Х₂₃ = 15, что приводит к вычеркиванию столбца 3, а значения объема производства в строке 2 становится =10. Наименьшая невычеркнутая стоимость С₁₁ = 10. Поскольку остаток объема производства в строке 1 и остаток спроса в столбце 1 = 0, Х₁₁= 0.

При вычеркивании столбца 1 «остаток» объема производства в строке 1= 0. Остальные базисные переменные имеют значения Х₁₄ = 0 и Х₂₄ = 10. Суммарные затраты, соответствуют этому решению равны 0 * 10 + 15 * 0 + 0 * 11 + 15 *- 9 + 10 * 20 + 5 * 0 = 335 долл., что лучше результата, полученного при использовании северо-западного угла.

Приближенный метод Фогеля (ПМФ).

Этот метод является эвристическим и обычно приводит к лучшему начальному решению, чем два описанных выше. На самом деле ПМФ часто дает оптимальное или близкое к оптимальному начальное решение.

Алгоритм состоит из следующих шагов.

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

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

Шаг 3. (а) Если невычеркнутой остается в точности одна строка или один столбец, то закончить вычисления.

(б). Если невычеркнутой только одна строка (столбец) с положительным объемом производства (спросом), найти базисные переменные в этой строке (столбце), используя метод наименьшей стоимости.

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

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

Пункты назначения.

Исходные пункты					Объем производства
	Х11 10	Х12 0	Х13 20	Х14 11
	Х21 12	Х22 7	Х23 9	Х24 20
	Х31 0	Х32 14	Х33 16	Х34 18
Спрос

Таблица 2 содержит первый набор штрафов для строк и столбцов. Поскольку строка 3 имеет наибольший штраф (= 14) и С₃₁ = 0, является наименьшим коэффициентом стоимости в этой строке, переменной Х₃₁ приписывается значение 5. Ограничения по строке 3 и столбцу 1 выполняются одновременно. Пусть вычеркивается столбец 1. Остаток объема производства для строки 3 = 0.

Таблица 2.

	1				Штрафы для строк
	10	0	20	11	15 10
	12	7	9	20	25 2
	5 0	14	16	18	5 14
Штрафы для столбцов

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

Таблица 3.

	1		3		Штрафы для строк
	10	0	20	11	15 11 11
	12	7	9	20	25 10 2 13
	5 0				5 0 - -
Штрафы для столбцов	5 -		15 - -

Строке 1 и столбцу 3 соответствуют одинаковые штрафы. При выборе столбца 3 переменная Х₂₃ принимает значение 15, в результате чего столбец 3 вычеркивается, а объем производства в строке 2 становится равным 10.

Последовательное применение ПМФ дает Х₂₂ = 10 (вычеркнуть строку 1) и Х₃₄ = 0 (Проверьте!) Суммарные затраты равны 315 долл.

Таким образом, полученное решение оказалось оптимальным.

Данный вариант ПМФ не включает правила выбора из одинаковых штрафов. Однако тот или иной выбор из одинаковых штрафов может оказать серьезное влияние на получение хорошего начального решения.

Например, если в таблице 3 вместо столбца 3 выбрать строку, то получится худшее начальное решение. (Покажете, что при этом будет найдено решение Х₁₂ = 15; Х₂₃ = 15; Х₂₄ = 10; Х₃₁ = 5. Суммарные затраты составят 335 долл.)

Упражнение: Повторите решение задачи, используя ПМФ и заменяя значение С₁₂ на 2 (вместо 0). При одновременном выполнении ограничений по строке и столбцу всегда вычеркивайте строку.

Ответ: Последовательность нахождения значений переменных дает Х₃₁ = 5 Х₂₃ = 15, Х₂₂ = 10 Х₁₄ = 10 Х₁₂ = 5 Х₁₁ = 0.

МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ

Задача управления запасами возникает, когда необходимо создать запас материальных ресурсов или предметов потребления с целью удовлетворения спроса на заданном интервале времени (конечном или бесконечном). Для обеспечения непрерывного и эффективного функционирования практически любой организации необходимо создание запасов.

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