Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лабораторная работа - Контрольная работа по прикладной математике - файл задача 7.rtf


Лабораторная работа - Контрольная работа по прикладной математике
скачать (145.2 kb.)

Доступные файлы (5):

Задача 10.doc88kb.19.04.2010 13:21скачать
задача 6.doc361kb.18.01.2011 18:28скачать
задача 7.rtf147kb.18.04.2010 10:05скачать
задача 8.xls29kb.18.04.2010 10:35скачать
задача 9.xls27kb.18.04.2010 10:59скачать

задача 7.rtf

Задача 7.

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


1


2


3


4


5


Запасы


1


27


36


35


31


29


250


2


22


23


26


32


35


200


3


35


42


38


32


39


200


Потребности


120


130


100


160


140



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


Условие баланса соблюдается. Запасы равны потребностям.

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


1


2


3


4


5


Запасы


1


27


36


35


31


29


250


2


22


23


26


32


35


200


3


35


42


38


32


39


200


Потребности


120


130


100


160


140



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


1


2


3


4


5


Запасы


1


27


36


35


31[110]


29[140]


250


2


22[120]


23[80]


26


32


35


200


3


35


42[50]


38[100]


32[50]


39


200


Потребности


120


130


100


160


140



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

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

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


v1=0


v2=41


v3=37


v4=31


v5=29


u1=0


27


36


35


31[110]


29[140]


u2=-18


22[120]


23[80]


26


32


35


u3=1


35


42[50]


38[100]


32[50]


39


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

(1;2): 0 + 41 > 36

(1;3): 0 + 37 > 35

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

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


1


2


3


4


5


Запасы


1


27


36[+]


35


31[110][-]


29[140]


250


2


22[120]


23[80]


26


32


35


200


3


35


42[50][-]


38[100]


32[50][+]


39


200


Потребности


120


130


100


160


140



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


1


2


3


4


5


Запасы


1


27


36[50]


35


31[60]


29[140]


250


2


22[120]


23[80]


26


32


35


200


3


35


42


38[100]


32[100]


39


200


Потребности


120


130


100


160


140



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


v1=0


v2=36


v3=37


v4=31


v5=29


u1=0


27


36[50]


35


31[60]


29[140]


u2=-13


22[120]


23[80]


26


32


35


u3=1


35


42


38[100]


32[100]


39


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

(1;3): 0 + 37 > 35

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

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


1


2


3


4


5


Запасы


1


27


36[50]


35[+]


31[60][-]


29[140]


250


2


22[120]


23[80]


26


32


35


200


3


35


42


38[100][-]


32[100][+]


39


200


Потребности


120


130


100


160


140



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


1


2


3


4


5


Запасы


1


27


36[50]


35[60]


31


29[140]


250


2


22[120]


23[80]


26


32


35


200


3


35


42


38[40]


32[160]


39


200


Потребности


120


130


100


160


140



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


v1=0


v2=36


v3=35


v4=29


v5=29


u1=0


27


36[50]


35[60]


31


29[140]


u2=-13


22[120]


23[80]


26


32


35


u3=3


35


42


38[40]


32[160]


39


Опорный план является оптимальным.

Затраты составят:

F(x) = 36*50 + 35*60 + 29*140 + 22*120 + 23*80 + 38*40 + 32*160 = 19080


Скачать файл (145.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации