Методическое пособие для выполнения контрольной работы по дисциплине
жүктеу/скачать 0.49 Mb.
|
| 3. Метод аппроксимации Фогеля
Основным недостатком метода минимального элемента является неучет будущих тарифов: в первых шагах алгоритма тарифы минимальны, на заключительных шагах возможно использование перевозок с высокими тарифами, тем самым, опорный план будетотличаться от оптимального, хотя и не так сильно, какв методе северо-западного угла. Метод аппроксимации Фогеля лишен выше указанных недостатков, однако довольно сложен для исполнения по сравнению двумя предыдущими методами. Алгоритм метода Фогеля состоит в следующем: На каждой итерации вычисляют по всем столбцам и строкам разность между двумя записанными в них минимальными тарифами, Среди указанных разностей выбирают максимальную. В строке (или столбце) с выбранной разностью определяют минимальный тариф и заполняют ее, полностью удовлетворяя потребности или полностью исчерпав запасы. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующим (ей) наибольшей разности между двумя минимальными тарифами, находящимися в данном (ей) столбце (строке). Строка с израсходованным запасом или столбец с удовлетворенной потребностью исключаются из рассмотрения, и в соответствующей разности ставится прочерк. Рассмотрим процесс составления опорного плана по методу Фогеля. На первом шаге разности между двумя соседними минимальными тарифами равны для строк (2-1=1. 5-4=1, 3-2=1), для столбцов (7-4=3, 5-2=3, 3-1=2, 6-2=4). Максимальная разность имеет место для четвертого столбца (4). Заполняем клетку А1B4, удовлетворив всю потребность четвертого предприятия, в результате чего у первого поставщика останется 50 единиц сырья, а четвертый столбец исключается из дальнейшего рассмотрения (вместо разностей ставится прочерк). На втором шаге итерации вычислим разности между соседними минимальными тарифами оставшихся клеток для строк (7-1=6, 5-4=1, 3-2=1) и для столбцов (7-4=3, 5-2=3, 3-1=2). Максимальная разность будет для первой строки (6). Заполняем клетку А1B3, исчерпав оставшееся сырье первого поставщика, при этом третьему потребителю нужно еще 190-50=140 единиц сырья. В итоге из рассмотрения исключаем первую строку. На следующем этапе разности равны для строк (5-4=1, 3-2=1) и для столбцов (9-4=5, 5-2=3, 9-3=6). Максимальная разность у третьего столбца (6). Заполняем клетку А3B3, полностью удовлетворив потребности третьего предприятия, в результате чего у третьего производителя останется 170-140=30 единиц сырья. Из дальнейшего рассмотрения исключаем третий столбец. Далее разности равны для строк (5-4=1, 9-2=7) и для столбцов (9-4=5, 5-2=3). Разность максимальной будет для третьей строки. Следовательно, заполняем клетку А3B2, исключив из последующих шагов третью строку. На последнем шаге остается только одна разность для второй строки (5-4=1). Поэтому заполняем оставшиеся клетки данной строки в порядке возрастания тарифов, сначала клетку А2B1, затем А2B2. В результате опорный план будет задаваться следующей матрицей: , при этом общая стоимость перевозок составит: Q=1*50+2*110+4*120+5*20+2*30+3*140=1330 условных единиц. Сравнение трех методов нахождения опорного плана позволяет сделать вывод, что план, самый близкий к оптимальному, дает метод аппроксимации Фогеля. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|