Методы оптимальных решений

6 задач ...

Задача 87

Ниже приведены расширенные матрицы для 100 вариантов систем линейных уравнений. Во всех вариантах .
Необходимо, применяя метод полного исключения неизвестных (Жордана-Гаусса), найти любое общее и три базисных решения системы. Сделать проверку. Решение рекомендуется представить в виде таблицы.
7 4 5 1 6 8
2 -8 17 10 12 9
3 11 13 -9 14 15

Задача 287

В каждом варианте приведены таблицы, в которых записаны условия канонической задачи линейного программирования на минимум, т. е. В первой строке помещены коэффициенты целевой функции. В остальных строках, в первых пяти столбцах, находятся векторы условий, а в последнем столбце записан вектор ограничений. В правом верхнем углу таблицы указана цель задачи.
Необходимо последовательно выполнить следующие задания.
1. Задачу решить графическим методом (см. пример 2.7).
2. Применяя симплекс-метод, решить задачу или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса (см. пример 2.9).
3. Построить двойственную задачу. Если вектор найден, вычислить оптимальный план двойственной задачи, используя первую теорему двойственности . Вычислить значение функции (см. пример 2.13).
4. Провести анализ полученного решения, применяя условия дополняющей нежесткости (см. пример 2.14).
Если , то . Если , то .
6 7 18 -5 1 min
1 5 -10 2 5 20
2 3 4 0 1 12
3 4 6 3 2 33




Задача 487

Ниже приведены комплексные задачи линейного программирования. Необходимо выполнить в указанном порядке следующие задания.
1. Найти оптимальный план прямой задачи графическим методом.
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план прямой задачи симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
5. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п.4). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
6. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи, найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, полученным графическим методом (см. п.1).

Задача 587
Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.
46 38 43 10 50 67
15 20 12 7 18 59
25 45 41 13 35 73
39 24 29 8 37 82
61 65 50 59 46





Задача 687
Ниже приведено 100 вариантов транспортной задачи в сетевой постановке. Каждая задача изображена в виде неориентированного связного графа. На ребрах записаны значения удельных стоимостей , на вершинах (в кружках) – значения запасов-потребностей . Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.
Задача 787
Ниже приведены таблицы, в клетках которых проставлены элементы матрицы эффективностей задачи о разборчивой невесте. Необходимо найти оптимальный вариант выбора, при котором средняя продолжительность семейной жизни каждой семьи будет наибольшей. Решить задачу методом потенциалов и венгерским методом.

Задание: выполнить задачи №№ 87, 287, 487, 587, 687, 787

12345Запасы1463843[50][-]10[17][+]5067215[59][-]2012[+]71859325[2][+]454113[42][-]35[29]7343924[65]29837[17]82Потребности6165505946Цикл приведен в таблице (2,3; 2,1; 3,1; 3,4; 1,4; 1,3; ). 12345Запасы1463843[8]10[59]5067215[17]2012[42]71859325[44]45411335[29]7343924[65]29837[17]82Потребности6165505946Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v3 = 43; 0 + v3 = 43; v3 = 43 u2 + v3 = 12; 43 + u2 = 12; u2 = -31 u2 + v1 = 15; -31 + v1 = 15; v1 = 46 u3 + v1 = 25; 46 + u3 = 25; u3 = -21 u3 + v5 = 35; -21 + v5 = 35; v5 = 56 u4 + v5 = 37; 56 + u4 = 37; u4 = -19 u4 + v2 = 24; -19 + v2 = 24; v2 = 43 u1 + v4 = 10; 0 + v4 = 10; v4 = 10 v1=46v2=43v3=43v4=10v5=56u1=0463843[8]10[59]50u2=-3115[17]2012[42]718u3=-2125[44]45411335[29]u4=-193924[65]29837[17]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (1;2): 0 + 43 > 38; ∆12 = 0 + 43 - 38 = 5 (1;5): 0 + 56 > 50; ∆15 = 0 + 56 - 50 = 6 (2;5): -31 + 56 > 18; ∆25 = -31 + 56 - 18 = 7 max(5,6,7) = 7 Выбираем максимальную оценку свободной клетки (2;5): 18 Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы1463843[8]10[59]5067215[17][-]2012[42]718[+]59325[44][+]45411335[29][-]7343924[65]29837[17]82Потребности6165505946Цикл приведен в таблице (2,5; 2,1; 3,1; 3,5; ). 12345Запасы1463843[8]10[59]50672152012[42]718[17]59325[61]45411335[12]7343924[65]29837[17]82Потребности6165505946Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v3 = 43; 0 + v3 = 43; v3 = 43 u2 + v3 = 12; 43 + u2 = 12; u2 = -31 u2 + v5 = 18; -31 + v5 = 18; v5 = 49 u3 + v5 = 35; 49 + u3 = 35; u3 = -14 u3 + v1 = 25; -14 + v1 = 25; v1 = 39 u4 + v5 = 37; 49 + u4 = 37; u4 = -12 u4 + v2 = 24; -12 + v2 = 24; v2 = 36 u1 + v4 = 10; 0 + v4 = 10; v4 = 10 v1=39v2=36v3=43v4=10v5=49u1=0463843[8]10[59]50u2=-31152012[42]718[17]u3=-1425[61]45411335[12]u4=-123924[65]29837[17]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (4;3): -12 + 43 > 29; ∆43 = -12 + 43 - 29 = 2 Выбираем максимальную оценку свободной клетки (4;3): 29 Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы1463843[8]10[59]50672152012[42][-]718[17][+]59325[61]45411335[12]7343924[65]29[+]837[17][-]82Потребности6165505946Цикл приведен в таблице (4,3; 4,5; 2,5; 2,3; ). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 5) = 17. Прибавляем 17 к объемам грузов, стоящих в плюсовых клетках и вычитаем 17 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 12345Запасы1463843[8]10[59]50672152012[25]718[34]59325[61]45411335[12]7343924[65]29[17]83782Потребности6165505946Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v3 = 43; 0 + v3 = 43; v3 = 43 u2 + v3 = 12; 43 + u2 = 12; u2 = -31 u2 + v5 = 18; -31 + v5 = 18; v5 = 49 u3 + v5 = 35; 49 + u3 = 35; u3 = -14 u3 + v1 = 25; -14 + v1 = 25; v1 = 39 u4 + v3 = 29; 43 + u4 = 29; u4 = -14 u4 + v2 = 24; -14 + v2 = 24; v2 = 38 u1 + v4 = 10; 0 + v4 = 10; v4 = 10 v1=39v2=38v3=43v4=10v5=49u1=0463843[8]10[59]50u2=-31152012[25]718[34]u3=-1425[61]45411335[12]u4=-143924[65]29[17]837Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij. Минимальные затраты составят: F(x) = 43*8 + 10*59 + 12*25 + 18*34 + 25*61 + 35*12 + 24*65 + 29*17 = 5844 Построим начальный план методом «минимального элемента»:Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Искомый элемент равен 7 Для этого элемента запасы равны 59, потребности 59. Поскольку минимальным является 59, то вычитаем его. x24 = min(59,59) = 59. 463843x5067xxx7x59 - 59 = 0254541x3573392429x378261655059 - 59 = 0460 Искомый элемент равен 24 Для этого элемента запасы равны 82, потребности 65. Поскольку минимальным является 65, то вычитаем его. x42 = min(82,65) = 65. 46x43x5067xxx7x025x41x3573392429x3782 - 65 = 176165 - 65 = 0500460 Искомый элемент равен 25 Для этого элемента запасы равны 73, потребности 61. Поскольку минимальным является 61, то вычитаем его. x31 = min(73,61) = 61. xx43x5067xxx7x025x41x3573 - 61 = 12x2429x371761 - 61 = 00500460 Искомый элемент равен 29 Для этого элемента запасы равны 17, потребности 50. Поскольку минимальным является 17, то вычитаем его. x43 = min(17,50) = 17. xx43x5067xxx7x025x41x3512x2429xx17 - 17 = 00050 - 17 = 330460 Искомый элемент равен 35 Для этого элемента запасы равны 12, потребности 46. Поскольку минимальным является 12, то вычитаем его. x35 = min(12,46) = 12. xx43x5067xxx7x025xxx3512 - 12 = 0x2429xx00033046 - 12 = 340 Искомый элемент равен 43 Для этого элемента запасы равны 67, потребности 33. Поскольку минимальным является 33, то вычитаем его. x13 = min(67,33) = 33. xx43x5067 - 33 = 34xxx7x025xxx350x2429xx00033 - 33 = 00340 Искомый элемент равен 50 Для этого элемента запасы равны 34, потребности 34. Поскольку минимальным является 34, то вычитаем его. x15 = min(34,34) = 34. xx43x5034 - 34 = 0xxx7x025xxx350x2429xx0000034 - 34 = 00 12345Запасы1463843[33]1050[34]6721520127[59]1859325[61]45411335[12]7343924[65]29[17]83782Потребности6165505946Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно: F(x) = 43*33 + 50*34 + 7*59 + 25*61 + 35*12 + 24*65 + 29*17 = 7530 Искомый элемент равен 8 Для этого элемента запасы равны 82, потребности 59. Поскольку минимальным является 59, то вычитаем его. x44 = min(82,59) = 59. 463843x5067152012x1859254541x357339242983782 - 59 = 2361655059 - 59 = 0460 Искомый элемент равен 12 Для этого элемента запасы равны 59, потребности 50. Поскольку минимальным является 50, то вычитаем его. x23 = min(59,50) = 50. 4638xx5067152012x1859 - 50 = 92545xx35733924x83723616550 - 50 = 00460 Искомый элемент равен 15 Для этого элемента запасы равны 9, потребности 61. Поскольку минимальным является 9, то вычитаем его. x21 = min(9,61) = 9. 4638xx506715x12xx9 - 9 = 02545xx35733924x8372361 - 9 = 526500460 Искомый элемент равен 24 Для этого элемента запасы равны 23, потребности 65. Поскольку минимальным является 23, то вычитаем его. x42 = min(23,65) = 23. 4638xx506715x12xx02545xx3573x24x8x23 - 23 = 05265 - 23 = 4200460 Искомый элемент равен 25 Для этого элемента запасы равны 73, потребности 52. Поскольку минимальным является 52, то вычитаем его. x31 = min(73,52) = 52. x38xx506715x12xx02545xx3573 - 52 = 21x24x8x052 - 52 = 04200460 Искомый элемент равен 35 Для этого элемента запасы равны 21, потребности 46. Поскольку минимальным является 21, то вычитаем его. x35 = min(21,46) = 21. x38xx506715x12xx025xxx3521 - 21 = 0x24x8x00420046 - 21 = 250 Искомый элемент равен 38 Для этого элемента запасы равны 67, потребности 42. Поскольку минимальным является 42, то вычитаем его. x12 = min(67,42) = 42. x38xx5067 - 42 = 2515x12xx025xxx350x24x8x0042 - 42 = 000250 Искомый элемент равен 50 Для этого элемента запасы равны 25, потребности 25. Поскольку минимальным является 25, то вычитаем его. x15 = min(25,25) = 25. x38xx5025 - 25 = 015x12xx025xxx350x24x8x0000025 - 25 = 00 12345Запасы14638[42]431050[25]67215[9]2012[50]71859325[52]45411335[21]7343924[23]298[59]3782Потребности6165505946В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 38*42 + 50*25 + 15*9 + 12*50 + 25*52 + 35*21 + 24*23 + 8*59 = 6640 Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v2 = 38; 0 + v2 = 38; v2 = 38 u4 + v2 = 24; 38 + u4 = 24; u4 = -14 u4 + v4 = 8; -14 + v4 = 8; v4 = 22 u1 + v5 = 50; 0 + v5 = 50; v5 = 50 u3 + v5 = 35; 50 + u3 = 35; u3 = -15 u3 + v1 = 25; -15 + v1 = 25; v1 = 40 u2 + v1 = 15; 40 + u2 = 15; u2 = -25 u2 + v3 = 12; -25 + v3 = 12; v3 = 37 v1=40v2=38v3=37v4=22v5=50u1=04638[42]431050[25]u2=-2515[9]2012[50]718u3=-1525[52]45411335[21]u4=-143924[23]298[59]37Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (1;4): 0 + 22 > 10; ∆14 = 0 + 22 - 10 = 12 (2;5): -25 + 50 > 18; ∆25 = -25 + 50 - 18 = 7 max(12,7) = 12 Выбираем максимальную оценку свободной клетки (1;4): 10 Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы14638[42][-]4310[+]50[25]67215[9]2012[50]71859325[52]45411335[21]7343924[23][+]298[59][-]3782Потребности6165505946Цикл приведен в таблице (1,4; 1,2; 4,2; 4,4; ). 12345Запасы146384310[42]50[25]67215[9]2012[50]71859325[52]45411335[21]7343924[65]298[17]3782Потребности6165505946Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v4 = 10; 0 + v4 = 10; v4 = 10 u4 + v4 = 8; 10 + u4 = 8; u4 = -2 u4 + v2 = 24; -2 + v2 = 24; v2 = 26 u1 + v5 = 50; 0 + v5 = 50; v5 = 50 u3 + v5 = 35; 50 + u3 = 35; u3 = -15 u3 + v1 = 25; -15 + v1 = 25; v1 = 40 u2 + v1 = 15; 40 + u2 = 15; u2 = -25 u2 + v3 = 12; -25 + v3 = 12; v3 = 37 v1=40v2=26v3=37v4=10v5=50u1=046384310[42]50[25]u2=-2515[9]2012[50]718u3=-1525[52]45411335[21]u4=-23924[65]298[17]37Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (2;5): -25 + 50 > 18; ∆25 = -25 + 50 - 18 = 7 (4;3): -2 + 37 > 29; ∆43 = -2 + 37 - 29 = 6 (4;5): -2 + 50 > 37; ∆45 = -2 + 50 - 37 = 11 max(7,6,11) = 11 Выбираем максимальную оценку свободной клетки (4;5): 37 Для этого в перспективную клетку (4;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы146384310[42][+]50[25][-]67215[9]2012[50]71859325[52]45411335[21]7343924[65]298[17][-]37[+]82Потребности6165505946Цикл приведен в таблице (4,5; 4,4; 1,4; 1,5; ). 12345Запасы146384310[59]50[8]67215[9]2012[50]71859325[52]45411335[21]7343924[65]29837[17]82Потребности6165505946Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v4 = 10; 0 + v4 = 10; v4 = 10 u1 + v5 = 50; 0 + v5 = 50; v5 = 50 u3 + v5 = 35; 50 + u3 = 35; u3 = -15 u3 + v1 = 25; -15 + v1 = 25; v1 = 40 u2 + v1 = 15; 40 + u2 = 15; u2 = -25 u2 + v3 = 12; -25 + v3 = 12; v3 = 37 u4 + v5 = 37; 50 + u4 = 37; u4 = -13 u4 + v2 = 24; -13 + v2 = 24; v2 = 37 v1=40v2=37v3=37v4=10v5=50u1=046384310[59]50[8]u2=-2515[9]2012[50]718u3=-1525[52]45411335[21]u4=-133924[65]29837[17]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (2;5): -25 + 50 > 18; ∆25 = -25 + 50 - 18 = 7 Выбираем максимальную оценку свободной клетки (2;5): 18 Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы146384310[59]50[8]67215[9][-]2012[50]718[+]59325[52][+]45411335[21][-]7343924[65]29837[17]82Потребности6165505946Цикл приведен в таблице (2,5; 2,1; 3,1; 3,5; ). 12345Запасы146384310[59]50[8]672152012[50]718[9]59325[61]45411335[12]7343924[65]29837[17]82Потребности6165505946Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v4 = 10; 0 + v4 = 10; v4 = 10 u1 + v5 = 50; 0 + v5 = 50; v5 = 50 u2 + v5 = 18; 50 + u2 = 18; u2 = -32 u2 + v3 = 12; -32 + v3 = 12; v3 = 44 u3 + v5 = 35; 50 + u3 = 35; u3 = -15 u3 + v1 = 25; -15 + v1 = 25; v1 = 40 u4 + v5 = 37; 50 + u4 = 37; u4 = -13 u4 + v2 = 24; -13 + v2 = 24; v2 = 37 v1=40v2=37v3=44v4=10v5=50u1=046384310[59]50[8]u2=-32152012[50]718[9]u3=-1525[61]45411335[12]u4=-133924[65]29837[17]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (1;3): 0 + 44 > 43; ∆13 = 0 + 44 - 43 = 1 (4;3): -13 + 44 > 29; ∆43 = -13 + 44 - 29 = 2 max(1,2) = 2 Выбираем максимальную оценку свободной клетки (4;3): 29 Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы146384310[59]50[8]672152012[50][-]718[9][+]59325[61]45411335[12]7343924[65]29[+]837[17][-]82Потребности6165505946Цикл приведен в таблице (4,3; 4,5; 2,5; 2,3; ). 12345Запасы146384310[59]50[8]672152012[33]718[26]59325[61]45411335[12]7343924[65]29[17]83782Потребности6165505946Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v4 = 10; 0 + v4 = 10; v4 = 10 u1 + v5 = 50; 0 + v5 = 50; v5 = 50 u2 + v5 = 18; 50 + u2 = 18; u2 = -32 u2 + v3 = 12; -32 + v3 = 12; v3 = 44 u4 + v3 = 29; 44 + u4 = 29; u4 = -15 u4 + v2 = 24; -15 + v2 = 24; v2 = 39 u3 + v5 = 35; 50 + u3 = 35; u3 = -15 u3 + v1 = 25; -15 + v1 = 25; v1 = 40 v1=40v2=39v3=44v4=10v5=50u1=046384310[59]50[8]u2=-32152012[33]718[26]u3=-1525[61]45411335[12]u4=-153924[65]29[17]837Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (1;2): 0 + 39 > 38; ∆12 = 0 + 39 - 38 = 1 (1;3): 0 + 44 > 43; ∆13 = 0 + 44 - 43 = 1 max(1,1) = 1 Выбираем максимальную оценку свободной клетки (1;2): 38 Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы14638[+]4310[59]50[8][-]672152012[33][-]718[26][+]59325[61]45411335[12]7343924[65][-]29[17][+]83782Потребности6165505946Цикл приведен в таблице (1,2; 1,5; 2,5; 2,3; 4,3; 4,2; ). 12345Запасы14638[8]4310[59]50672152012[25]718[34]59325[61]45411335[12]7343924[57]29[25]83782Потребности6165505946Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v2 = 38; 0 + v2 = 38; v2 = 38 u4 + v2 = 24; 38 + u4 = 24; u4 = -14 u4 + v3 = 29; -14 + v3 = 29; v3 = 43 u2 + v3 = 12; 43 + u2 = 12; u2 = -31 u2 + v5 = 18; -31 + v5 = 18; v5 = 49 u3 + v5 = 35; 49 + u3 = 35; u3 = -14 u3 + v1 = 25; -14 + v1 = 25; v1 = 39 u1 + v4 = 10; 0 + v4 = 10; v4 = 10 v1=39v2=38v3=43v4=10v5=49u1=04638[8]4310[59]50u2=-31152012[25]718[34]u3=-1425[61]45411335[12]u4=-143924[57]29[25]837Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij. Минимальные затраты составят: F(x) = 38*8 + 10*59 + 12*25 + 18*34 + 25*61 + 35*12 + 24*57 + 29*25 = 5844Построим начальный план методом ФогеляИспользуя метод Фогеля, построим первый опорный план транспортной задачи. Находим разности по строкам. Для строки N=1 первый минимальный элемент min11 = 10, второй минимальный элемент min21 = 38. Их разность равна d = min21 - min11 = 28. Для строки N=2 первый минимальный элемент min12 = 7, второй минимальный элемент min22 = 12. Их разность равна d = min22 - min12 = 5. Для строки N=3 первый минимальный элемент min13 = 13, второй минимальный элемент min23 = 25. Их разность равна d = min23 - min13 = 12. Для строки N=4 первый минимальный элемент min14 = 8, второй минимальный элемент min24 = 24. Их разность равна d = min24 - min14 = 16. Находим разности по столбцам. Для столбца N=1 первый минимальный элемент min11 = 15. второй минимальный элемент min21 25. Их разность d = min21 - min11 = 10. Для столбца N=2 первый минимальный элемент min12 = 20. второй минимальный элемент min22 24. Их разность d = min22 - min12 = 4. Для столбца N=3 первый минимальный элемент min13 = 12. второй минимальный элемент min23 29. Их разность d = min23 - min13 = 17. Для столбца N=4 первый минимальный элемент min14 = 7. второй минимальный элемент min24 8. Их разность d = min24 - min14 = 1. Для столбца N=5 первый минимальный элемент min15 = 18. второй минимальный элемент min25 35. Их разность d = min25 - min15 = 17. Вычислив все эти разности, видим, что наибольшая из них соответствует строке (1). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (4). 12345ЗапасыРазности по строкам146384310506728215201271859532545411335731243924298378216Потребности616550594600Разности по столбцам104171170 Искомый элемент равен 10 Для этого элемента запасы равны 67, потребности 59. Поскольку минимальным является 59, то вычитаем его. x14 = min(67,59) = 59. 0000067 - 59 = 80xxxxx000xx0000xx000059 - 59 = 0x0 Находим разности по строкам. Для строки N=1 первый минимальный элемент min11 = 38, второй минимальный элемент min21 = 43. Их разность равна d = min21 - min11 = 5. Для строки N=2 первый минимальный элемент min12 = 12, второй минимальный элемент min22 = 15. Их разность равна d = min22 - min12 = 3. Для строки N=3 первый минимальный элемент min13 = 25, второй минимальный элемент min23 = 35. Их разность равна d = min23 - min13 = 10. Для строки N=4 первый минимальный элемент min14 = 24, второй минимальный элемент min24 = 29. Их разность равна d = min24 - min14 = 5. Находим разности по столбцам. Для столбца N=1 первый минимальный элемент min11 = 15. второй минимальный элемент min21 25. Их разность d = min21 - min11 = 10. Для столбца N=2 первый минимальный элемент min12 = 20. второй минимальный элемент min22 24. Их разность d = min22 - min12 = 4. Для столбца N=3 первый минимальный элемент min13 = 12. второй минимальный элемент min23 29. Их разность d = min23 - min13 = 17. Для столбца N=5 первый минимальный элемент min15 = 18. второй минимальный элемент min25 35. Их разность d = min25 - min15 = 17. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (5). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (5). 12345ЗапасыРазности по строкам146384310508521520127185933254541133573104392429837825Потребности61655004600Разности по столбцам10417-170 Искомый элемент равен 18 Для этого элемента запасы равны 59, потребности 46. Поскольку минимальным является 46, то вычитаем его. x25 = min(59,46) = 46. 0000x00000059 - 46 = 130xxxxx0000xx000046 - 46 = 0x Находим разности по строкам. Для строки N=1 первый минимальный элемент min11 = 38, второй минимальный элемент min21 = 43. Их разность равна d = min21 - min11 = 5. Для строки N=2 первый минимальный элемент min12 = 12, второй минимальный элемент min22 = 15. Их разность равна d = min22 - min12 = 3. Для строки N=3 первый минимальный элемент min13 = 25, второй минимальный элемент min23 = 41. Их разность равна d = min23 - min13 = 16. Для строки N=4 первый минимальный элемент min14 = 24, второй минимальный элемент min24 = 29. Их разность равна d = min24 - min14 = 5. Находим разности по столбцам. Для столбца N=1 первый минимальный элемент min11 = 15. второй минимальный элемент min21 25. Их разность d = min21 - min11 = 10. Для столбца N=2 первый минимальный элемент min12 = 20.