Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Потребность третьего пункта назначения удовлетворена полностью





Математическая модель транспортной задачи:

F = ∑∑cijxij, (1)

при условиях:

∑xij = ai, i = 1,2,…, m, (2)

∑xij = bj, j = 1,2,…, n, (3)

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

        Запасы
         
         
         
Потребности        

 

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 60 + 50 + 20 = 130

∑b = 80 + 40 + 30 = 150

Занесем исходные данные в распределительную таблицу.

        Запасы
         
         
         
         
Потребности        

 

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

        Запасы
  2[30]   3[30]  
  0[50]      
    1[20]    
    0[20]    
Потребности        

 

2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 6. Следовательно, опорный план является вырожденным.

Строим новый план.

Значение целевой функции для этого опорного плана равно:

        Запасы
  2[60]      
  0[10] 1[40]    
  2[10]   3[10]  
      0[20]  
Потребности        

 

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

  v1=2 v2=3 v3=3
u1=0 2[60]    
u2=-2 0[10] 1[40]  
u3=0 2[10]   3[10]
u4=-3     0[20]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

Выбираем максимальную оценку свободной клетки (3;2): 1

Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

        Запасы
  2[60]      
  0[10][+] 1[40][-]    
  2[10][-] 1[+] 3[10]  
      0[20]  
Потребности        

 

Цикл приведен в таблице (3,2; 3,1; 2,1; 2,2;).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

        Запасы
  2[60]      
  0[20] 1[30]    
    1[10] 3[10]  
      0[20]  
Потребности        

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

  v1=2 v2=3 v3=5
u1=0 2[60]    
u2=-2 0[20] 1[30]  
u3=-2   1[10] 3[10]
u4=-5     0[20]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

Выбираем максимальную оценку свободной клетки (1;3): 3

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

        Запасы
  2[60][-]   3[+]  
  0[20][+] 1[30][-]    
    1[10][+] 3[10][-]  
      0[20]  
Потребности        

 

Цикл приведен в таблице (1,3; 1,1; 2,1; 2,2; 3,2; 3,3;).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

        Запасы
  2[50]   3[10]  
  0[30] 1[20]    
    1[20]    
      0[20]  
Потребности        

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

  v1=2 v2=3 v3=3
u1=0 2[50]   3[10]
u2=-2 0[30] 1[20]  
u3=-2   1[20]  
u4=-3     0[20]

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 2*50 + 3*10 + 0*30 + 1*20 + 1*20 + 0*20 = 170

 

Date: 2015-07-25; view: 393; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию