Стандартная форма линейных оптимизационных моделей 7 страница
Таблица (1а).
 0 10
|  15 0
|  20
|  0 11
| ||
 12
|  0 7
|  15 9
|  10 20
| ||
 5 0
|  14
|  16
|  18
| ||
В таблице (1а) приведено начальное решение, полученное следующим образом: Х12 и Х31 – переменные, которым соответствуют минимальные стоимости (С12 = С31 = 0). Выберем произвольно Х12. Соответственно значения спроса и объема производства определяют Х12 = 15, то есть и по строке, и по столбцу ограничения выполняются. После вычерчивания столбца 2 объем производства в строке 1 остается равным нулю. Теперь среди оставшихся элементов минимальная стоимость соответствует переменной Х31. Значения Х31 = 5 удовлетворяет ограничениям и по столбцу 1, и по строке 3. После вычеркивания строки 3 оставшийся спрос в столбце 1 = 0. Наименьший невычеркнутый элемент – С23 = 9.
Ограничения на спрос и объем производства определяют Х23 = 15, что приводит к вычеркиванию столбца 3, а значения объема производства в строке 2 становится =10. Наименьшая невычеркнутая стоимость С11 = 10. Поскольку остаток объема производства в строке 1 и остаток спроса в столбце 1 = 0, Х11= 0.
При вычеркивании столбца 1 «остаток» объема производства в строке 1= 0. Остальные базисные переменные имеют значения Х14 = 0 и Х24 = 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) и С31 = 0, является наименьшим коэффициентом стоимости в этой строке, переменной Х31 приписывается значение 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 переменная Х23 принимает значение 15, в результате чего столбец 3 вычеркивается, а объем производства в строке 2 становится равным 10.
Последовательное применение ПМФ дает Х22 = 10 (вычеркнуть строку 1) и Х34 = 0 (Проверьте!) Суммарные затраты равны 315 долл.
Таким образом, полученное решение оказалось оптимальным.
Данный вариант ПМФ не включает правила выбора из одинаковых штрафов. Однако тот или иной выбор из одинаковых штрафов может оказать серьезное влияние на получение хорошего начального решения.
|
|
|
Например, если в таблице 3 вместо столбца 3 выбрать строку, то получится худшее начальное решение. (Покажете, что при этом будет найдено решение Х12 = 15; Х23 = 15; Х24 = 10; Х31 = 5. Суммарные затраты составят 335 долл.)
Упражнение: Повторите решение задачи, используя ПМФ и заменяя значение С12 на 2 (вместо 0). При одновременном выполнении ограничений по строке и столбцу всегда вычеркивайте строку.
Ответ: Последовательность нахождения значений переменных дает Х31 = 5 Х23 = 15, Х22 = 10 Х14 = 10 Х12 = 5 Х11 = 0.
МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ
Задача управления запасами возникает, когда необходимо создать запас материальных ресурсов или предметов потребления с целью удовлетворения спроса на заданном интервале времени (конечном или бесконечном). Для обеспечения непрерывного и эффективного функционирования практически любой организации необходимо создание запасов.
Дата добавления: 2016-01-06; просмотров: 11; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!