Найти оптимальное решение транспортной задачи. Необходимо, чтобы потребность третьего пункта удовлетворялась полностью
| Si | Pj | |||
|---|---|---|---|---|
| 5 | 6 | 13 | ||
| 8 | 4 | 4 | 3 | |
| 10 | 2 | 1 | 6 | |
| 2 | 3 | 2 | 4 | |
Решить транспортную задачу. Заданы мощности поставщиков ai(i=1,2,3), ёмкости потребителей bj(j=1,2,3) и матрица затрат времени перевозок единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные транспортные затраты времени наименьшие.
| ai | bj | |||
|---|---|---|---|---|
| 16 | 20 | 12 | 12 | |
| 25 | 16 | 7 | 5 | 3 |
| 25 | 5 | 6 | 4 | 20 |
| 10 | 9 | 10 | 6 | 7 |
Решение
Первый этап решения транспортной задачи сводится к определению её типа, открытой она является или закрытой. Закрытой называют задачу у которой потребности и возможности равны между собой.
Сумма ai = 25 + 25 + 10 = 60
Сумма bj = 16 + 20 + 12 + 12 = 60
Так как ai = bj, то задача является закрытой.
Второй этап - поиск опорного плана методом "наименьшей стоимости". Среди всех стоимостей наименьшей является - 3. Для этой величины ai = 25 (см. строку) и bj = 12 (см. столбец). min(25,12) = 12, вычтем эту величину из 25 и 12. Получим новую таблицу.
| ai | bj | |||
|---|---|---|---|---|
| 16 | 20 | 12 | 0 | |
| 13 | 16 | 7 | 5 | - |
| 25 | 5 | 6 | 4 | X |
| 10 | 9 | 10 | 6 | X |
Повторим этап. Среди всех стоимостей наименьшей является - 4. Для этой величины ai = 25 (см. строку) и bj = 12 (см. столбец). min(25,12) = 12, вычтем эту величину из 25 и 12. Получим новую таблицу.
| ai | bj | |||
|---|---|---|---|---|
| 16 | 20 | 0 | 0 | |
| 13 | 16 | 7 | X | - |
| 13 | 5 | 6 | - | X |
| 10 | 9 | 10 | X | X |
И снова повторим этап. Среди всех стоимостей наименьшей является - 5. Для этой величины ai = 13 (см. строку) и bj = 16 (см. столбец). min(13,16) = 13, вычтем эту величину из 13 и 16. Получим новую таблицу. В этом случае нулю равна величина ai, поэтому вычёркиваем строку.
| ai | bj | |||
|---|---|---|---|---|
| 3 | 20 | 0 | 0 | |
| 13 | 16 | 7 | X | - |
| 0 | - | X | - | X |
| 10 | 9 | 10 | X | X |
Повторим этап. Среди всех стоимостей наименьшей является - 7. Для этой величины ai = 13 (см. строку) и bj = 20 (см. столбец). min(13,20) = 13, вычтем эту величину из 13 и 20. Получим новую таблицу. В этом случае нулю равна величина ai, поэтому вычёркиваем строку.
| ai | bj | |||
|---|---|---|---|---|
| 3 | 7 | 0 | 0 | |
| 0 | X | - | X | - |
| 0 | - | X | - | X |
| 10 | 9 | 10 | X | X |
Этап 2 можно повторить ещё два раза, но смысла нет, так как осталась единственная строка и необходимо удовлетворить все оставшиеся потребности.
| ai | bj | |||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 0 | X | - | X | - |
| 0 | - | X | - | X |
| 0 | - | - | X | X |
Подсчитав количество прочерков в таблице и убедившись, что их количество равно m+n-1, где m - количество столбцов, n - количество строк, считаем, что найден опорный невырожденный план .
| ai | bj | |||
|---|---|---|---|---|
| 16 | 20 | 12 | 12 | |
| 25 | 16 | 7 [13] | 5 | 3 [12] |
| 25 | 5 [13] | 6 | 4 [12] | 20 |
| 10 | 9 [3] | 10 [7] | 6 | 7 |
Сумма чисел находящихся в квадратных скобках по каждой строке и каждому столбцу равны соотвтетственно ai и bj.
Подсчитаем, чему равна целевая функция.
F = 7*13 + 3*12 + 5*13 + 4*12 + 9*3 + 10*7 = 91 + 36 + 65 + 48 + 27 + 70 = 337
Третий этап. Для проверки оптимальности плана необходимо найти предварительные потенциалы, используя клетки таблицы с прямоугольными скобками.
Положим u1 = 0.
u1 + v2 = 7
0 + v2 = 7
v2 = 7
u1 + v4 = 3
0 + v4 = 3
v4 = 3
u3 + v2 = 10
u3 + 7 = 10
u3 = 3
u3 + v1 = 9
3 + v1 = 9
v1 = 6
u2 + v1 = 5
u2 + 6 = 5
u2 = -1
u2 + v3 = 4
-1 + v3 = 4
v3 = 5
Разместим данные в таблице. В круглые скобки поместим сумму ui и vj.
| ai | bj | |||
|---|---|---|---|---|
| v1=6 | v2=7 | v3=5 | v4=3 | |
| u1=0 | (6) 16 | (7) 7 [13] | (5) 5 | (3) 3 [12] |
| u2=-1 | (5) 5 [13] | (6) 6 | (4) 4 [12] | (2) 20 |
| u3=3 | (9) 9 [3] | (10) 10 [7] | (8) 6 | (6) 7 |
Если хотя бы в одной клетке значение в скобках оказывается больше, чем значение цены, то план не является оптимальным, следует продолжить работу.
План не явлется оптимальным (для v3 и u3 сумма равна 8, что больше 6).
Найти кратчайший путь от вершины х0 до всех остальных вершин графа. Граф описывается перечнем всех своих дуг xixj и их длинами lij. Дуга xixj кратко обозначается парой чисел i, j, длина lij задаётся одним числом. Так, например, дуга x3x5 обозначается парой чисел 3,5 и т.п.
Данные заданы в таблице. Верхняя строка содержит перечень дуг. Строчка таблицы содержит длины дуг номера которых указаны в верхней строке.
| uij | 0,1 | 0,2 | 0,3 | 1,4 | 1,6 | 2,4 | 2,5 | 3,5 | 3,6 | 4,7 | 4,8 | 5,4 | 5,8 | 6,8 | 7,8 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| lij | 11 | 12 | 16 | 4 | 17 | 7 | 9 | 14 | 11 | 9 | 21 | 22 | 8 | 11 | 13 |
Необходимо составить сетевой график и определить минимальное время (в днях) выполнения производственного задания. Проследить длиннейшую технологическую цепочку и в двух-трёх случаях указать, какие работы и на сколько могут быть ускорены для сокращения времени выполнения всего задания. Продолжительности работ и последжовательность их выполнения заданы в таблице (для каждой работы указано, после окончания каких работ может быть начато её выполнение). Вместо названий работы задаются условно их номерами.
| Работа | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Срок | 15 | 15 | 25 | 25 | 20 | 20 | 30 | 30 | 25 | 20 | 25 | 25 | 20 | 20 | 30 | 30 | 20 | 20 | 25 | 20 |
| После работ | 4 | 4 | - | 3 | 3 | 1,3 | 3 | 7 | 5,8 | 6,8 | 7 | 2,9 | 10,12 | 6,11 | 13,14 | 6,11 | 12,14 | 16,17 | 10,18 | 15,19 |
Найти оптимальную стратегию и цену игры. Сделать проверку, если дана матрица игры А.
| 5 | -3 | 2 | -4 |
| 1 | 2 | -1 | 3 |
| 2 | 2 | 1 | 4 |