Автор работы: Пользователь скрыл имя, 08 Апреля 2014 в 00:38, контрольная работа
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
Распределительный метод является одним из вариантов базового симплексного метода. Поэтому идея распределительного метода (как и симплексного) содержит такие же три существенных момента.
Транспортная задача линейного программирования 3
Задача материальный запас 18
Задача склад 19
Задача транспорт 20
Задача распределение 21
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
4 |
5 |
6 |
Запасы | |
1 |
5 |
4 |
6 |
8 |
9 |
3[25] |
25 |
2 |
4[20] |
5 |
8 |
3 |
1[15] |
6 |
35 |
3 |
6[10] |
3[10] |
2[15] |
1[25] |
5 |
8 |
60 |
4 |
8 |
6 |
5 |
2 |
4[40] |
7[25] |
65 |
Потребности |
30 |
10 |
15 |
25 |
55 |
50 |
3*25 + 4*20 + 1*15 + 6*10 + 3*10 + 2*15 + 1*25 + 4*40 + 7*25 = 650
Шаг 6. Определяем оценку для каждой свободной клетки.
(1;1): В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,1; 1,6; 4,6; 4,5; 2,5; 2,1; ).
Оценка свободной клетки равна Δ11 = (5) - (3) + (7) - (4) + (1) - (4) = 2.
(1;2): В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,2; 1,6; 4,6; 4,5; 2,5; 2,1; 3,1; 3,2; ).
Оценка свободной клетки равна Δ12 = (4) - (3) + (7) - (4) + (1) - (4) + (6) - (3) = 4.
(1;3): В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,3; 1,6; 4,6; 4,5; 2,5; 2,1; 3,1; 3,3; ).
Оценка свободной клетки равна Δ13 = (6) - (3) + (7) - (4) + (1) - (4) + (6) - (2) = 7.
(1;4): В свободную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,4; 1,6; 4,6; 4,5; 2,5; 2,1; 3,1; 3,4; ).
Оценка свободной клетки равна Δ14 = (8) - (3) + (7) - (4) + (1) - (4) + (6) - (1) = 10.
(1;5): В свободную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,5; 1,6; 4,6; 4,5; ).
Оценка свободной клетки равна Δ15 = (9) - (3) + (7) - (4) = 9.
(2;2): В свободную клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,2; 2,1; 3,1; 3,2; ).
Оценка свободной клетки равна Δ22 = (5) - (4) + (6) - (3) = 4.
(2;3): В свободную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,3; 2,1; 3,1; 3,3; ).
Оценка свободной клетки равна Δ23 = (8) - (4) + (6) - (2) = 8.
(2;4): В свободную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,4; 2,1; 3,1; 3,4; ).
Оценка свободной клетки равна Δ24 = (3) - (4) + (6) - (1) = 4.
(2;6): В свободную клетку (2;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,6; 2,5; 4,5; 4,6; ).
Оценка свободной клетки равна Δ26 = (6) - (1) + (4) - (7) = 2.
(3;5): В свободную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,5; 3,1; 2,1; 2,5; ).
Оценка свободной клетки равна Δ35 = (5) - (6) + (4) - (1) = 2.
(3;6): В свободную клетку (3;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,6; 3,1; 2,1; 2,5; 4,5; 4,6; ).
Оценка свободной клетки равна Δ36 = (8) - (6) + (4) - (1) + (4) - (7) = 2.
(4;1): В свободную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,1; 4,5; 2,5; 2,1; ).
Оценка свободной клетки равна Δ41 = (8) - (4) + (1) - (4) = 1.
(4;2): В свободную клетку (4;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,2; 4,5; 2,5; 2,1; 3,1; 3,2; ).
Оценка свободной клетки равна Δ42 = (6) - (4) + (1) - (4) + (6) - (3) = 2.
(4;3): В свободную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,3; 4,5; 2,5; 2,1; 3,1; 3,3; ).
Оценка свободной клетки равна Δ43 = (5) - (4) + (1) - (4) + (6) - (2) = 2.
(4;4): В свободную клетку (4;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,4; 4,5; 2,5; 2,1; 3,1; 3,4; ).
Оценка свободной клетки равна Δ44 = (2) - (4) + (1) - (4) + (6) - (1) = 0.
Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Fx невозможно, поскольку она достигла минимального значения.
Таким образом, последний опорный план является оптимальным.
Минимальные затраты составят:
3*25 + 4*20 + 1*15 + 6*10 + 3*10 + 2*15 + 1*25 + 4*40 + 7*25 = 650
Если в оптимальном решении задачи имеется несколько оценок равных нулю, то это является свидетельством того, что среди бесчисленного множества решений этой задачи существуют еще решения, являющиеся также оптимальными, поскольку значение целевой функции остается одинаковым — минимальным. Их принято называть альтернативными.
Примечание. Основной алгоритм распределительного метода является не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [mп—(m+n—1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20 — 361 цикл.
Анализ оптимального плана.
Из 1-го склада необходимо весь груз направить в 6-й магазин
Из 2-го склада необходимо груз направить в 1-й магазин (20), в 5-й магазин (15)
Из 3-го склада необходимо груз направить в 1-й магазин (10), в 2-й магазин (10), в 3-й магазин (15), в 4-й магазин (25)
Из 4-го склада необходимо груз направить в 5-й магазин (40), в 6-й магазин (25)
2.Задача материальный запас
Определить величину текущего запаса и страховой запас.
N поставки |
Дата поставки |
Объем поставки |
Интервал поставки |
1 |
1 янв |
62 |
1 |
2 |
11 янв |
123 |
10 |
3 |
27 янв |
180 |
16 |
4 |
7 фев |
60 |
11 |
5 |
18 фев |
40 |
11 |
6 |
1 мар |
130 |
11 |
7 |
12 мар |
190 |
11 |
8 |
25 мар |
62 |
13 |
≈ 11 дней
≈11 дней
≈ 4 дня
Определить максимальный уровень запаса в системе с фиксированным уровнем запаса.
Зстрах = 200 ед.
S = 4 ед.
L = 10 дн.
R = 4 дн.
M = Зстрах+S*(L+R) = 200+4*(10+4) = 256 ед.
3.Задача склад
Перевозка грузов со склада в цех производится по одностороннему маятниковому маршруту. Грузы упакованы в коробки по 20 кг. И перевозятся на электрокарах на расстояние 600 м. Грузопоток 35т. в смену. Средний вес груза, перевозившего за 1 рейс 1,2м. Определить необходимое количество электрокаров, если норма времени внутри цеха с грузом - 8,256 (tпр) мин/рейс, без груза - 6,220 мин/рейс, между цехами с грузом - 6,41 мин/рейс, между цехами без груза - 4,293 мин/рейс, a для электрокара 1,19.
4.Задача транспорт