<jupyter_start><jupyter_text>Лабораторная работа №1-2 Разработка программного средства на основе алгоритмов методов нахождения приоритетного решения с использованием количественной оценки (методы угла, метод наименьшего элемента, метод циклических перестановок, метод потенциалов) Транспортная задачаТранспортная задача — это математическая задача по нахождению оптимального распределения поставок однородного «товара» (груза, вещества) между пунктами отправления и назначения при заданных, численно выраженных затратах (стоимостях, расходах) на перевозку. Общее решение изначально описано методами линейной алгебры, как для задачи линейного программирования специального вида. Транспортная задача может быть представлена на письме в виде прямоугольной таблицы.*Пример задачи*:В $ {m} $ пунктах производства $A_{1}, ..., A_{m}$ находится однородный продукт (сахар, уголь, картофель и т. д.) в количествах соответственно $a_{1}, ..., a_{m}$, который должен быть доставлен $ {n} $ потребителям $B_{1}, ..., B_{n}$ в количествах $ b_{1}, ..., b_{n}$. Известны транспортные издержки $ c_{ij} $ (расходы), связанные с перевозкой единицы продукции из пункта $ A_{i} $ в пункт $ B_{j} $.Требуется составить такой план перевозок, который обеспечивал бы при минимальных транспортных издержках удовлетворение спроса всех пунктов потребления за счет распределения всего продукта, произведенного всеми пунктами производства.Для разрешимости поставленной задачи необходимо и достаточно, чтобы сумма запасов равнялась сумме спроса всех пунктов, т. е.$ \sum_{i=1}^{m} a_{i} = \sum_{j=1}^{n} b_{j} $Для наглядности транспортную задачу представим в виде таблицы, которая называется распределительной.![распределительная таблица](./data/table.png)Здесь количество груза, перевозимого из $ i $-гo пункта отправления в $ j $-й пункт назначения, равно $x_{ij}$, запас груза в $ i $-м пункте отправления измеряется величиной $ a_{i} \geqslant 0 $, а потребность $ j $-го пункта назначения в грузе равна $ b_{j} \geqslant 0 $. Поскольку отрицательные перевозки не имеют реального смысла для данной задачи (обратная перевозка от пунктов назначения в пункты отправления), будем предполагать, что $ x_{ij} \geqslant 0 $.Матрица $(c_{ij})_{m \times n}$ называется матрицей тарифов (издержек или транспортных расходов), а числа $c_{ij}$ — тарифами. Планом транспортной задачи называется матрица $X=(x_{ij})_{m \times n}$ где каждое число $x_{ij}$ обозначает количество единиц груза, которое надо доставить из $i$-го пункта отправления в $j$-й пункт назначения. Матрицу $X$ называют еще матрицей перевозок.Общие суммарные затраты, связанные с реализацией плана перевозок, можно представить целевой функцией$f=c_{11}x_{11}+c_{12}x_{12}+ ... +c_{1n}x_{1n}+ ... +c_{m1}x_{m1}+c_{m2}x_{m2}+ ... +c_{mn}x_{mn} = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}x_{ij}$Переменные $x_{ij}$ должны удовлетворять ограничениям по запасам, по потребностям и условиям неотрицательности.Данные условия образуют систему ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.Система ограничений задачи содержит $m+n$ уравнений с $mn$ переменными $x_{ij}$.Для транспортной задачи важное значение имеет следующая теорема. Ранг матрицы транспортной задачи на единицу меньше числа уравнений, т. е. $r=m+n-1$.Из теоремы следует, что каждый опорный план имеет $m+n-1$ базисных переменных и $mn-(m+n-1)=(m-1) \times (n-1)$ свободных переменных, равных нулю.Транспортные задачи будем решать с помощью общего приема последовательного улучшения планов, состоящего изследующих основных этапов: 1. определения исходного опорного плана; 2. оценки этого плана; 3. перехода к следующему плану путем однократного замещения одной базисной переменной на свободную.  Метод северо-западного углаДля составления исходного плана перевозок удобно пользоваться правилом «северо-западного угла», которое состоит в следующем. Будем заполнять таблицу начиная с левого верхнего (северо-западного) угла, двигаясь далее по строке вправо или по столбцу вниз. Занесем в клетку (1, 1) меньшее из чисел $ a_{1} $ и $ b_{1} $ т. е.$ x_{11}=min(a_{1}; b_{1}) $.Если $a_{1}>b_{1}$, то $x_{11}=b_{1}$ и первый столбец «закрыт» для заполнения остальных его клеток, т. е. $x_{i1} = 0$ для $i = 2, 3, ..., m$ (потребности первого потребителя удовлетворены полностью).Двигаясь далее по первой строке, записываем в соседнюю клетку (1,2) меньшее из чисел $a_{1}-b_{1}$ и $b_{2}$, т. е.$x_{12}=min(a_{1}-b_{1}; b_{2})$.Если $b_{1} > a_{1}$, то аналогично «закрывается» первая строка, т, е. $x_{1k}=0$ для $k = 2, 3, ..., n$. Переходим к заполнению соседней клетки (2, 1), куда заносим $x_{21}=min(a_{2}; b_{1}-a_{1})$.Заполнив вторую клетку (1,2) или (2, 1), переходим к заполнению следующей, третьей клетки либо по второй строке, либо по второму столбцу. Будем продолжать этот процесс до полного исчерпания груза у поставщиков или полного удовлетворения потребителей. Последняя заполненная клетка $(m,n)$ окажется лежащей в последнем $n$-м столбце и в последней$m$-й строке.После получения опорного плана необходимо проверить его на невырожденность.Правило: количество базисных (заполненных) клеток в первоначальном плане ВСЕГДА должно быть равно $m + n - 1$, где $m$ - количество поставщиков, $n$ - количество потребителей транспортной задачи.Что же делать, если количество заполненных ячеек опорного плана меньше необходимого?На некотором шаге получения первоначального плана может сложиться ситуация, когда одновременно удовлетворяются потребности магазина и опустошается склад.  В этом случае происходит "потеря" базисной клетки. Это приводит к тому, что система определения потенциалов имеет не единственное решение. Чтобы обойти эту ситуацию, добавим к базисным ячейкам недостающее количество ячеек с нулевыми значениями. Нулевое значение поставим в клетку, стоящую рядом с базисной клеткой, которая обусловила "пропажу" базисного значения. План, полученный по правилу «северо-западного угла», будет опорным планом системы ограничений задачи. Решение задачи*Входные данные:*<jupyter_code>suppliers, consumers, costs, capacity = initProgram('data/Problem5.json', isPrint=True)<jupyter_output>B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>    ] [< 8>    ] [< 4>    ] [<10>    ] [< 6>    ] [< 9>    ]     23
A2     [< 6>    ] [< 9>    ] [< 8>    ] [< 5>    ] [<11>    ] [<15>    ]     32
A3     [< 9>    ] [< 5>    ] [<14>    ] [<11>    ] [<12>    ] [< 6>    ]     12
A4     [<14>    ] [< 3>    ] [< 6>    ] [<10>    ] [< 4>    ] [< 8>    ]     15
A5     [< 9>    ] [< 5>    ] [<10>    ] [<15>    ] [< 3>    ] [<12>    ]     16
A6     [< 8>    ] [< 4>    ] [<10>    ] [<10>    ] [<12>    ] [<15>    ]     20
DEMAND         32         11         17         14         21         23 

Проверка исходных данных на сбалансированность: задача сбалансирована, ∑a=∑b=118.0<jupyter_text>*Исходный код решения:*<jupyter_code>def northWest(suppliers, consumers, costs, capacity, isPrint=False):
    consumer_index = 0
    supp = np.array(suppliers, copy=True)
    cons = np.array(consumers, copy=True)
    lost_basis = []
    while consumer_index < len(cons):
        supplier_index = 0
        while supplier_index < len(supp):
            consumer = cons[consumer_index]
            supplier = supp[supplier_index]
            if consumer == 0:
                break
            if supplier == 0:
                supplier_index += 1
                continue
            # проверка "потери" базисной клетки
            if supplier == consumer and supplier_index != len(supp)-1 and consumer_index != len(cons)-1:
                lost_basis.insert(0, (supplier_index, consumer_index+1))
            # выбираем наименьшее количество товара, которое возможно переместить
            capacity[supplier_index][consumer_index] = min(supplier, consumer)
            # вычитаем получившееся количество товара у поставщика и потребителя
            cons[consumer_index] -= capacity[supplier_index][consumer_index]
            supp[supplier_index] -= capacity[supplier_index][consumer_index]
            supplier_index += 1
            if isPrint:
                print()
                PrintOut(supp, cons, costs, capacity)
        consumer_index += 1

    # вычисляем индексы ненулевых значений матрицы перевозок
    a = tuple(map(tuple, np.transpose(np.nonzero(capacity))))

    # маскируем все нулевые элементы матрицы перевозок
    capacity = ma.array(capacity)
    capacity = ma.masked_equal(capacity, 0)
    # удаляем маску на "пропавших" базисных элементах
    for i in lost_basis:
        capacity[i] = ma.nomask
    
    if isPrint:
        print('\nПолучившийся опорный план:')
        PrintOut(suppliers, consumers, costs, capacity)
    return capacity<jupyter_output><empty_output><jupyter_text>*Результат выполнения:*<jupyter_code>northWestCap = northWest(suppliers, consumers, costs, capacity, isPrint=True)<jupyter_output>B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>(23)] [< 8>( 0)] [< 4>( 0)] [<10>( 0)] [< 6>( 0)] [< 9>( 0)]      0
A2     [< 6>( 0)] [< 9>( 0)] [< 8>( 0)] [< 5>( 0)] [<11>( 0)] [<15>( 0)]     32
A3     [< 9>( 0)] [< 5>( 0)] [<14>( 0)] [<11>( 0)] [<12>( 0)] [< 6>( 0)]     12
A4     [<14>( 0)] [< 3>( 0)] [< 6>( 0)] [<10>( 0)] [< 4>( 0)] [< 8>( 0)]     15
A5     [< 9>( 0)] [< 5>( 0)] [<10>( 0)] [<15>( 0)] [< 3>( 0)] [<12>( 0)]     16
A6     [< 8>( 0)] [< 4>( 0)] [<10>( 0)] [<10>( 0)] [<12>( 0)] [<15>( 0)]     20
DEMAND          9         11         17         14         21         23 
Стоимость:  207

       B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>(23)] [< 8>( 0)] [< 4>( 0)] [<10>( 0)] [< 6>( 0)] [< 9>( 0)]      0
A2     [< 6>( 9)] [< 9>( 0)] [< 8>( 0)] [< 5>( 0)] [<11>( 0)] [<15>( 0)]     23
A3     [< 9>( 0)] [< 5>( 0)] [<14>( 0)] [<11>( 0)] [<12>( 0)] [< 6>( 0)]     12
A4     [<14>( 0)] [< 3>( 0)][...]<jupyter_text>Метод наименьшего элементаИсходный опорный план, построенный по правилу «северо-западного угла», обычно оказывается весьма далеким от оптимального, так как при его определении игнорируются величины затрат $c_{ij}$. Поэтому в дальнейших расчетах потребуется много операций для достижения оптимального плана. Число итераций можно сократить, если исходный план строить по более-усовершенствованному правилу «наименьшего элемента». Сущность его состоит в том, что на каждом шаге осуществляется максимально возможная поставка в клетку с минимальным тарифом $c_{ik}$. Заполнение таблицы начинаем с клетки, которой соответствует наименьший элемент $c_{ik}$ из всей матрицы тарифов. Затем остаток по столбцу или строке помещаем в клетку того же столбца или строки, которой соответствует следующее по величине значение $c_{ik}$ и т. д. Иными словами, последовательность заполняемых клеток определяется по величине $c_{ik}$, а помещаемые в этихклетках величины $x_{ik}$ как и в правиле «северо-западного угла».Может оказаться, что при построении опорного плана занятых клеток будет меньше чем $m+n-1$. В этом случае задача называется вырожденной. Тогда в свободную клетку (в ту, которой соответствует наименьший тариф) заносится «базисный» нуль, и эта клетка считается занятой. Решение задачи*Входные данные:*<jupyter_code>suppliers, consumers, costs, capacity = initProgram('data/Problem5.json', isPrint=True)<jupyter_output>B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>    ] [< 8>    ] [< 4>    ] [<10>    ] [< 6>    ] [< 9>    ]     23
A2     [< 6>    ] [< 9>    ] [< 8>    ] [< 5>    ] [<11>    ] [<15>    ]     32
A3     [< 9>    ] [< 5>    ] [<14>    ] [<11>    ] [<12>    ] [< 6>    ]     12
A4     [<14>    ] [< 3>    ] [< 6>    ] [<10>    ] [< 4>    ] [< 8>    ]     15
A5     [< 9>    ] [< 5>    ] [<10>    ] [<15>    ] [< 3>    ] [<12>    ]     16
A6     [< 8>    ] [< 4>    ] [<10>    ] [<10>    ] [<12>    ] [<15>    ]     20
DEMAND         32         11         17         14         21         23 

Проверка исходных данных на сбалансированность: задача сбалансирована, ∑a=∑b=118.0<jupyter_text>*Исходный код решения:*<jupyter_code>def minElem(suppliers, consumers, cost, cap, isPrint=False):
    costs = ma.array(cost, copy=True)
    supp = np.array(suppliers, copy=True)
    cons = np.array(consumers, copy=True)
    # пока все элементы матрицы перевозок не замаскированы
    while costs.mask.all() == False:
        # находим индекс минимального элемента матрицы тарифов
        idx = np.unravel_index(costs.argmin(), costs.shape)
        # выбираем наименьшее количество товара, которое возможно переместить
        if supp[idx[0]] < cons[idx[1]]:
            # записываем его в матрицу перевозок
            cap[idx] = supp[idx[0]]
            # маскируем строку матрицы тарифов
            costs[idx[0]] = ma.masked
        else:
            cap[idx] = cons[idx[1]]
            # маскируем столбец матрицы тарифов
            costs[:, idx[1]] = ma.masked
        # вычитаем получившееся количество товара у поставщика и потребителя
        supp[idx[0]] -= cap[idx]
        cons[idx[1]] -= cap[idx]
        if isPrint:
            print()
            PrintOut(supp, cons, cost, cap)

    costs.mask = ma.nomask
    # вычисляем индексы ненулевых значений матрицы перевозок
    a = tuple(map(tuple, np.transpose(np.nonzero(cap))))

    # маскируем все нулевые элементы матрицы перевозок
    cap = ma.array(cap)
    cap = ma.masked_equal(cap, 0)
    # проверка матрицы перевозок на вырожденность
    if cap.count() != (len(supp)+len(cons)-1):
        # маскируем элементы матрицы тарифов в соответствии
        # с ненулевыми элементами матрицы перевозок
        for i in a:
            costs[i] = ma.masked
        # добавляем недостающее количество базисных нулей в матрицу перевозок
        for _ in range(len(supp)+len(cons)-1 - cap.count()):
            # находим индекс минимального элемента матрицы тарифов
            idx = np.unravel_index(costs.argmin(), costs.shape)
            # маскируем этот элемент в матрице тарифов
            costs[idx] = ma.masked
            # удаляем маску этого элемента в матрице перевозок
            cap[idx] = ma.nomask
        
    if isPrint:
        print('\nПолучившийся опорный план:')
        PrintOut(suppliers, consumers, costs, cap)
    return cap<jupyter_output><empty_output><jupyter_text>*Результат выполнения:*<jupyter_code>minElCap = minElem(suppliers, consumers, costs, capacity, isPrint=True)<jupyter_output>B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>( 0)] [< 8>( 0)] [< 4>( 0)] [<10>( 0)] [< 6>( 0)] [< 9>( 0)]     23
A2     [< 6>( 0)] [< 9>( 0)] [< 8>( 0)] [< 5>( 0)] [<11>( 0)] [<15>( 0)]     32
A3     [< 9>( 0)] [< 5>( 0)] [<14>( 0)] [<11>( 0)] [<12>( 0)] [< 6>( 0)]     12
A4     [<14>( 0)] [< 3>(11)] [< 6>( 0)] [<10>( 0)] [< 4>( 0)] [< 8>( 0)]      4
A5     [< 9>( 0)] [< 5>( 0)] [<10>( 0)] [<15>( 0)] [< 3>( 0)] [<12>( 0)]     16
A6     [< 8>( 0)] [< 4>( 0)] [<10>( 0)] [<10>( 0)] [<12>( 0)] [<15>( 0)]     20
DEMAND         32          0         17         14         21         23 
Стоимость:  33

       B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>( 0)] [< 8>( 0)] [< 4>( 0)] [<10>( 0)] [< 6>( 0)] [< 9>( 0)]     23
A2     [< 6>( 0)] [< 9>( 0)] [< 8>( 0)] [< 5>( 0)] [<11>( 0)] [<15>( 0)]     32
A3     [< 9>( 0)] [< 5>( 0)] [<14>( 0)] [<11>( 0)] [<12>( 0)] [< 6>( 0)]     12
A4     [<14>( 0)] [< 3>(11)] [...]<jupyter_text>Сравнение с опорным планом, построенным по методу северо-западного угла:<jupyter_code>PrintOut(suppliers, consumers, costs, northWestCap)<jupyter_output>B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>(23)] [< 8>    ] [< 4>    ] [<10>    ] [< 6>    ] [< 9>    ]     23
A2     [< 6>( 9)] [< 9>(11)] [< 8>(12)] [< 5>    ] [<11>    ] [<15>    ]     32
A3     [< 9>    ] [< 5>    ] [<14>( 5)] [<11>( 7)] [<12>    ] [< 6>    ]     12
A4     [<14>    ] [< 3>    ] [< 6>    ] [<10>( 7)] [< 4>( 8)] [< 8>    ]     15
A5     [< 9>    ] [< 5>    ] [<10>    ] [<15>    ] [< 3>(13)] [<12>( 3)]     16
A6     [< 8>    ] [< 4>    ] [<10>    ] [<10>    ] [<12>    ] [<15>(20)]     20
DEMAND         32         11         17         14         21         23 
Стоимость:  1080<jupyter_text>Метод потенциаловСущность метода потенциалов состоит в следующем. После того, как найден исходный опорный план перевозок, каждому поставщику $A_{i}$ (каждой строке) ставится в соответствие некоторое число $u_{i} (\overline{\rm i=1, m})$, а каждому потребителю $B_{j}$ (каждому столбцу) — некоторое число $v_{j}$. Числа $u_{i}$ и $v_{j}$ называются потенциалами соответственно поставщика $A_{i}$ и потребителя $B_{j}$ и выбираются так, чтобы в любой загруженной клетке их сумма равнялась тарифу этой клетки, т. е. $u_{i}+v_{j}=c_{ij}$. Так как всех потенциалов $m+n$, а занятых клеток $m+n-1$, то для определения чисел $u_{i}$ и $v_{j}$ придется решать систему из $m+n-1$ уравнений $u_{i}+v_{j}=c_{ij}$ с $m+n$ неизвестными. В этом случае одной из неизвестных можно придать произвольное значение, и тогда система будет иметь единственное решение, т. е. все остальные $m+n-1$ неизвестных определятся однозначно.Затем для проверки оптимальности плана просматриваются свободные клетки $(i, j)$ и для каждой из них вычисляется разность $s_{ij}$ между тарифом $c_{ij}$ и суммой $u_{i}+v_{j}$ потенциалов строки и столбца. План оптимален, когда для каждой свободной клетки $(i, j)$ разность $s_{ij}$ есть величина неотрицательная, т. е. $s_{ij}=c_{ij}-(u_{i}+v_{j}) \geqslant 0$.Полученные разности называются оценками (характеристиками) свободных клеток. Отрицательные оценки указывают на перспективность клеток, загрузка их приведет к улучшению плана. Положительные и нулевые оценки исключают возможность улучшения полученного плана. Переход к новому плану осуществляется по общим правилам распределительногометода. Для наиболее перспективной клетки строится замкнутый контур, вершинам которого приписываются чередующиеся знаки (свободной клетке приписывается положительный знак). В клетках, соответствующих отрицательным вершинам, отыскивается наименьший груз, который и «перемещается» по клеткам замкнутого цикла, т. е. прибавляется к клеткам со знаком плюс, включая свободную, и вычитается из клеток со знаком минус.В новом плане вновь определяются потенциалы строк и столбцов и вычисляются оценки для всех свободных клеток. Когда среди оценок не окажется отрицательных, полученный план будет оптимальным.Итак, чтобы решить транспортную задачу методом потенциалов, необходимо:1. построить опорный план перевозок по одному из вышеизложенных правил;2. вычислить потенциалы $u_{i}$ и $v_{j}$ соответственно поставщиков и потребителей;3. вычислить суммы потенциалов (косвенные тарифы) для свободных клеток $u_{i}+v_{j}=c'_{ij}$;4. проверить разность $s_{ij}=c_{ij}-c'_{ij}$.Если все $s_{ij} \geqslant 0$ для свободных клеток, полученный план оптимален. Если хотя бы одна оценка $s_{ij} < 0$, в число занятых вводят клетку, для которой оценка минимальна, и получают новый план перевозок. Процесс продолжают до тех пор, пока не будет получен план, для которого все оценки $s_{ij} \geqslant 0$.Алгебраическая сумма $s_{ij}$ стоимостей по циклу пересчета свободной клетки $(i, j)$ равна разности между стоимостью $c_{ij}$ и суммой потенциалов $u_{i}$ и $v_{j}$, т. е.$s_{ij}=c_{ij}-c'_{ij}=c_{ij}-(u_{i}+v_{j})$. Решение задачиВозьмем опорные планы метода северо-западного угла и метода наименьшего элемента.*Входные данные:*<jupyter_code>suppliers, consumers, costs, capacity = initProgram('data/Problem5.json')
print(f'\nОпорный план метода северо-западного угла:')
PrintOut(suppliers, consumers, costs, northWestCap)
print(f'\nОпорный план метода наименьшего элемента:')
PrintOut(suppliers, consumers, costs, minElCap)<jupyter_output>Опорный план метода северо-западного угла:
       B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>(23)] [< 8>    ] [< 4>    ] [<10>    ] [< 6>    ] [< 9>    ]     23
A2     [< 6>( 9)] [< 9>(11)] [< 8>(12)] [< 5>    ] [<11>    ] [<15>    ]     32
A3     [< 9>    ] [< 5>    ] [<14>( 5)] [<11>( 7)] [<12>    ] [< 6>    ]     12
A4     [<14>    ] [< 3>    ] [< 6>    ] [<10>( 7)] [< 4>( 8)] [< 8>    ]     15
A5     [< 9>    ] [< 5>    ] [<10>    ] [<15>    ] [< 3>(13)] [<12>( 3)]     16
A6     [< 8>    ] [< 4>    ] [<10>    ] [<10>    ] [<12>    ] [<15>(20)]     20
DEMAND         32         11         17         14         21         23 
Стоимость:  1080

Опорный план метода наименьшего элемента:
       B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>    ] [< 8>    ] [< 4>(17)] [<10>    ] [< 6>( 1)] [< 9>( 5)]     23
A2     [< 6>(18)] [< 9>    ] [< 8>    ] [< 5>(14)] [<11>    ] [<15>    ]     32
A3     [< 9>    ] [< 5[...]<jupyter_text>*Исходный код решения:*<jupyter_code>def PrintP(supp, cons, costs, cap=None):
    nCost = 0
    n = len(supp)
    m = len(cons)
    print(' ' * 6, end=' ')
    for x in range(1, m + 1):
        colName = 'B' + str(x)
        print('{0:10}'.format(colName), end=' ')
    print('     U')
    for x in range(n):
        rowName = 'A' + str(x + 1)
        print('{0:6}'.format(rowName), end=' ')
        for y in range(m):
            if cap is not None and cap[x][y] is not ma.masked:
                print('[<%2i>(%2i)]' % (round(costs[x][y]), round(cap[x][y])), end=' ')
                nCost += costs[x][y] * cap[x][y]
            else:
                print('[<%2i>    ]' % (round(costs[x][y])), end=' ')
        print('%6s' % supp[x])
    print('V     ', end=' ')
    for x in range(m):
        print('%10s' % cons[x], end=' ')
    print()
    if cap is not None:
        print('Стоимость: ', int(round(nCost)))

def potential(costs, cap, isPrint=False):
    mask = ma.getmask(cap)
    u = ma.masked_all(costs.shape[0], dtype=int)
    v = ma.masked_all(costs.shape[1], dtype=int)
    # предположим, первый элемент матрицы u равен нулю
    u[0] = 0

    # вычисляем потенциалы u и v
    while True:
        i = 0
        j = 0
        # проходим по матрице стоимостей
        for row in mask:
            for el in row:
                # если стоимость замаскирована, невозможно вычислить u или v
                if el == True:
                    j += 1
                    continue
                # вычисляем u или v, если они еще не вычислены
                if ma.is_masked(u[i]) and not ma.is_masked(v[j]):
                    u[i] = costs[i][j] - v[j]
                if ma.is_masked(v[j]) and not ma.is_masked(u[i]):
                    v[j] = costs[i][j] - u[i]
                j += 1
            j = 0
            i += 1
            if isPrint:
                print()
                PrintP(u, v, costs, cap)
            
        # проверяем, все ли значения массивов u и v вычислены
        if not ma.is_masked(u) and not ma.is_masked(v):
            break

    # вычисляем косвенные тарифы
    indCosts = costs.copy()
    i = 0
    j = 0
    for row in mask:
        for el in row:
            if el == True:
                # s = c - c'; c' = u + v
                indCosts[i][j] = costs[i][j] - (u[i]+v[j])
            j += 1
        j = 0
        i += 1

    if isPrint:
        print()
        PrintP(u, v, indCosts, cap)
    # вычисляем индексы отрицательных значений матрицы косвенных тарифов
    costsIndex = tuple(map(tuple, np.transpose(np.where(indCosts < 0))))

    return u, v, indCosts, costsIndex<jupyter_output><empty_output><jupyter_text>*Результат выполнения:*<jupyter_code>print(f'Метод северо-западного угла:')
u, v, inderectCosts, costsIndex = potential(costs, northWestCap, isPrint=True)
print(f'\nПотенциальные клетки для загрузки (с отрицательными косвенными тарифами):{costsIndex}\n')
print(f'Метод наименьшего элемента:')
u, v, inderectCosts, costsIndex = potential(costs, minElCap, isPrint=True)
print(f'\nПотенциальные клетки для загрузки (с отрицательными косвенными тарифами):{costsIndex}\n')<jupyter_output>Метод северо-западного угла:

       B1         B2         B3         B4         B5         B6              U
A1     [< 9>(23)] [< 8>    ] [< 4>    ] [<10>    ] [< 6>    ] [< 9>    ]      0
A2     [< 6>( 9)] [< 9>(11)] [< 8>(12)] [< 5>    ] [<11>    ] [<15>    ]     --
A3     [< 9>    ] [< 5>    ] [<14>( 5)] [<11>( 7)] [<12>    ] [< 6>    ]     --
A4     [<14>    ] [< 3>    ] [< 6>    ] [<10>( 7)] [< 4>( 8)] [< 8>    ]     --
A5     [< 9>    ] [< 5>    ] [<10>    ] [<15>    ] [< 3>(13)] [<12>( 3)]     --
A6     [< 8>    ] [< 4>    ] [<10>    ] [<10>    ] [<12>    ] [<15>(20)]     --
V               9         --         --         --         --         -- 
Стоимость:  1080

       B1         B2         B3         B4         B5         B6              U
A1     [< 9>(23)] [< 8>    ] [< 4>    ] [<10>    ] [< 6>    ] [< 9>    ]      0
A2     [< 6>( 9)] [< 9>(11)] [< 8>(12)] [< 5>    ] [<11>    ] [<15>    ]     -3
A3     [< 9>    ] [< 5>    ] [<14>( 5)] [<11>( 7)] [<12>    ] [< 6>    ]     -[...]<jupyter_text>Метод циклических перестановокМетод циклических перестановок (распределительный метод) представляет собой разновидность симплексного, так как основан на аналогичном общем принципе расчета: вначале строится исходный опорный план перевозок по одному из вышеизложенных правил, а затем последовательно производится его улучшение до получения оптимального. Для этого для каждой свободной клетки строят замкнутый цикл.Набор клеток матрицы перевозок, в котором две и только две клетки расположены в одной строке или одном столбце и последняя клетка набора лежит в той же строке или столбце, что и первая, называется замкнутым циклом.Этот набор, или совокупность, клеток можно представить так:$(i_{1},j_{1}) \to (i_{1},j_{2}) \to (i_{2},j_{2}) \to ... \to (i_{s},j_{s}) \to (i_{s},j_{1}) $Графически замкнутый цикл представляет собой замкнутую ломаную линию, звено которой проходит либо только по строке, либо только по столбцу. Каждое звено соединяет две клетки цикла.Допустимый план транспортной задачи является опорным тогда и только тогда, когда из занятых этим планом клеток нельзя образовать ни одного цикла.Если в матрице перевозок содержится опорный план, то для каждой свободной клетки можно образовать и притом только один замкнутый цикл, содержащий эту свободную клетку и некоторую часть занятых клеток.Составляем опорный план, находим циклы. Тарифы в клетках, находящихся в нечетных вершинах цикла, берем со знаком плюс, а в четных — со знаком минус. По каждому циклу подсчитываем алгебраическую сумму тарифов.Если замкнутый цикл имеет вид$(i,j) \to (k,j) \to (k,l) \to (t,l) \to ... \to (u,v) \to (i,v) $,то$s_{ij} = c_{ij}-c_{kj}+c_{kl}-c_{tl}+ ... +c_{uv}-c_{iv}$где $(i, j)$ — свободная клетка.Если алгебраическая сумма $s_{ij}$ отрицательна, то путем изменения значений, стоящих в клетках замкнутого цикла, можно получить план с меньшим значением линейной формы.Критерием оптимальности при нахождении минимума функции служит неотрицательность алгебраических сумм $s_{ij}$. Если указанное требование не соблюдено, план не оптимален и подлежит улучшению.Вычисления при решении транспортной задачи распределительным методом ведутся по следующему алгоритму:1. исходные данные задачи располагают в распределительной таблице;2. строят исходный опорный план по правилу «северо-западного угла», или по правилу «минимального элемента», при этом должны оказаться занятыми $r=m+n-1$ клеток;3. производят оценку первой свободной клетки путем построения замкнутого цикла и вычисления по этому циклу величины $s_{ij}$. Если $s_{ij}<0$, то переходят к следующему пункту алгоритма;4. перемещают по циклу количество груза, равное наименьшему из чисел, размещенных в четных клетках цикла. Далее возвращаются к пункту 3. Если $s_{ij} \geqslant 0$, то оценивают следующую свободную клетку, и т. д., пока не обнаружат клетку с отрицательной оценкой. Среди всех клеток с оценкой меньше нуля нужно найти клетку с наибольшим нарушением оптимальности. Если, наконец, оценки всех свободных клеток окажутся неотрицательными, то оптимальное решение найдено.*Замечание:*На каждом этапе построения нового опорного плана при выполнении пункта 3 алгоритма целесообразно испытывать не все свободные клетки подряд, а выбирать для оценок в первую очередь клетки, имеющие относительно малые тарифы.Добавление возмущений к объемам спроса и предложенияЧтобы ситуация вырожденности не возникла, можно прибавить к объемам потребления небольшие возмущения — числа, обозначаемые $ε$, такие как $0,00001$, а также прибавить сумму этих чисел к объему одного из поставщиков, чтобы равенство суммарных объемов груза для поставщиков и потребителей не нарушалось. При получении итогового результата эти значения должны округляться. Данциг, ссылаясь на Ордена, утверждает, что ни одно допустимое базисное решение не будет вырожденным, если $0 < ε < 1/n$ — в этом случае решение не окажется зацикленным и алгоритм завершается через конечное число шагов. Гасс, ссылаясь на более раннюю статью Ордена, предлагает выбирать $ε < δ/2m$, где $δ$ — единица последнего значащего разряда $а_{i}$ и $b_{j}$. Совсем маленькие возмущения могут попадать на ошибки округления компьютеров, поэтому нужно выбрать значения, заведомо не выходящее за пределы точности используемого компьютером или платформой для вычислений формата вещественных чисел, и при этом имеющие ничтожное значение для перевозимого груза (например, миллиграммы при перевозках, измеряемых в килограммах или тоннах). Задача будет реализована с возмущениями $0,001$.  Решение задачиВозьмем опорные планы метода северо-западного угла и метода наименьшего элемента.*Входные данные:*<jupyter_code>aSupply, aDemand, aCost, capacity = initProgram('data/Problem5.json')
# add a small amount to prevent degeneracy
# degeneracy can occur when the sums of subsets of supply and demand equal
elipsis = 0.001
aSupply[1] += elipsis
northWestCap = northWest(aSupply, aDemand, aCost, capacity)
print(f'\nОпорный план метода северо-западного угла:')
PrintOut(aSupply, aDemand, aCost, northWestCap)
print()
aSupply, aDemand, aCost, capacity = initProgram('data/Problem5.json')
elipsis = 0.001
aSupply[1] += elipsis
minElCap = minElem(aSupply, aDemand, aCost, capacity)
print(f'\nОпорный план метода наименьшего элемента:')
PrintOut(aSupply, aDemand, aCost, minElCap)<jupyter_output>Опорный план метода северо-западного угла:
       B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>(23)] [< 8>    ] [< 4>    ] [<10>    ] [< 6>    ] [< 9>    ]     23
A2     [< 6>( 9)] [< 9>(11)] [< 8>(12)] [< 5>    ] [<11>    ] [<15>    ]     32
A3     [< 9>    ] [< 5>    ] [<14>( 5)] [<11>( 7)] [<12>    ] [< 6>    ]     12
A4     [<14>    ] [< 3>    ] [< 6>    ] [<10>( 7)] [< 4>( 8)] [< 8>    ]     15
A5     [< 9>    ] [< 5>    ] [<10>    ] [<15>    ] [< 3>(13)] [<12>( 3)]     16
A6     [< 8>    ] [< 4>    ] [<10>    ] [<10>    ] [<12>    ] [<15>(20)]     20
DEMAND         32         11         17         14         21         23 
Стоимость:  1080


Опорный план метода наименьшего элемента:
       B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>    ] [< 8>    ] [< 4>(17)] [<10>    ] [< 6>( 1)] [< 9>( 5)]     23
A2     [< 6>(18)] [< 9>    ] [< 8>    ] [< 5>(14)] [<11>    ] [<15>    ]     32
A3     [< 9>    ] [< [...]<jupyter_text>*Исходный код решения:*<jupyter_code>nVeryLargeNumber = 99999999999
n, m = aCost.shape
# индекс вакантной клетки
Pivot = (-1,-1)

def printOut(aRoute, aDual):
    nCost = 0
    print(' ' * 6, end=' ')
    for x in range(1, m + 1):
        colName = 'B' + str(x)
        print('{0:10}'.format(colName), end=' ')
    print('SUPPLY')
    for x in range(n):
        rowName = 'A' + str(x + 1)
        print('{0:6}'.format(rowName), end=' ')
        for y in range(m):
            if aRoute[x][y] is ma.masked:
                print('[<%2i>%4i]' % (round(aCost[x][y]), round(aDual[x][y])), end=' ')
            else:
                nCost += aCost[x][y] * aRoute[x][y]
                print('[<%2i>(%2i)]' % (round(aCost[x][y]), round(aRoute[x][y])), end=' ')
        print('%6i' % aSupply[x])
    print('DEMAND', end=' ')
    for x in range(m):
        print('%10i' % aDemand[x], end=' ')
    print('\nСтоимость: ', int(round(nCost)))

def NotOptimal(aDual, aRoute):
    global Pivot
    GetDual(aDual, aRoute)
    # индекс минимального элемента
    Pivot = np.unravel_index(aDual.argmin(), aDual.shape)
    return (aDual[Pivot] < 0)

def GetDual(aDual, aRoute):
    for u in range(0, n):
        for v in range(0, m):
            aDual[u][v] = ma.masked
            # если переменная не базисная
            if aRoute[u][v] is ma.masked:
                aPath = FindPath(aRoute, u, v)
                # подсчитываем по каждому циклу алгебраическую сумму тарифов
                z = 1
                x = 0
                for w in aPath:
                    x += z * aCost[w[0]][w[1]]
                    z *= -1
                aDual[u][v] = x

def FindPath(aRoute, u, v):
    aPath = [[u, v]]
    if not LookHorizontaly(aPath, aRoute, u, v, v):
        print('Path error, press key', u, v)
        input()
    return aPath

def LookHorizontaly(aPath, aRoute, u, v, v1):
    for i in range(0, m):
        if i != v and aRoute[u][i] is not ma.masked:
            # завершаем цикл, если элемент находится на этой же строке/столбце
            if i == v1:
                aPath.append([u, i])
                return True
            if LookVerticaly(aPath, aRoute, u, i, v1):
                aPath.append([u, i])
                return True
    return False

def LookVerticaly(aPath, aRoute, u, v, v1):
    for i in range(0, n):
        if i != u and aRoute[i][v] is not ma.masked:
            if LookHorizontaly(aPath, aRoute, i, v, v1):
                aPath.append([i, v])
                return True
    return False

def BetterOptimal(aRoute):
    aPath = FindPath(aRoute, Pivot[0], Pivot[1]) # поиск цикла для вакантной клетки
    print(f'\nЦикл: ({aPath})\n')
    nMin = nVeryLargeNumber
    for w in range(1, len(aPath), 2): # нахождение минимального значения нечетных вершин цикла
        t = aRoute[aPath[w][0]][aPath[w][1]]
        if t < nMin:
            ind = (aPath[w][0], aPath[w][1])
            nMin = t
    aRoute[Pivot] = ma.nomask
    for w in range(1, len(aPath), 2): # перераспределение груза - к нечетным прибавляем, у четных вычитаем
        aRoute[aPath[w][0]][aPath[w][1]] -= nMin
        aRoute[aPath[w - 1][0]][aPath[w - 1][1]] += nMin
    aRoute[ind] = ma.masked

def cycle(aRoute):
    # создание массива n * m, заполненный -1
    # aDual - матрица алгебраических сумм не базисных переменных
    aDual = ma.masked_all(aCost.shape)
    
    GetDual(aDual, aRoute)
    
    printOut(aRoute, aDual)

    # проверка оптимальности решения
    while NotOptimal(aDual, aRoute):
        print(f'\nВакантная клетка: ({Pivot})')
        # оптимизировать план
        BetterOptimal(aRoute)
        GetDual(aDual, aRoute)
        printOut(aRoute, aDual)
print(f'Метод северо-западного угла:')
cycle(northWestCap)
print(f'\nМетод наименьшего элемента:')
cycle(minElCap)<jupyter_output>Метод северо-западного угла:
       B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>(23)] [< 8>  -4] [< 4>  -7] [<10>   2] [< 6>   4] [< 9>  -2]     23
A2     [< 6>( 9)] [< 9>(11)] [< 8>(12)] [< 5>   0] [<11>  12] [<15>   7]     32
A3     [< 9>  -3] [< 5> -10] [<14>( 5)] [<11>( 7)] [<12>   7] [< 6>  -8]     12
A4     [<14>   3] [< 3> -11] [< 6>  -7] [<10>( 7)] [< 4>( 8)] [< 8>  -5]     15
A5     [< 9>  -1] [< 5>  -8] [<10>  -2] [<15>   6] [< 3>(13)] [<12>( 3)]     16
A6     [< 8>  -5] [< 4> -12] [<10>  -5] [<10>  -2] [<12>   6] [<15>(20)]     20
DEMAND         32         11         17         14         21         23 
Стоимость:  1080

Вакантная клетка: ((5, 1))

Цикл: ([[5, 1], [1, 1], [1, 2], [2, 2], [2, 3], [3, 3], [3, 4], [4, 4], [4, 5], [5, 5]])

       B1         B2         B3         B4         B5         B6         SUPPLY
A1     [< 9>(23)] [< 8>  -4] [< 4>  -7] [<10> -10] [< 6>  -8] [< 9> -14]     23
A2     [< 6>( 9)] [< 9>( 6)] [< 8>(17)] [[...]
{'fraction_non_alphanumeric': 0.1386970629836093, 'fraction_numerical': 0.04237734697839532, 'mean_word_length': 2.708526175048853, 'pattern_counts': {'":': 0, '<': 474, '<?xml version=': 0, '>': 463, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '462313', 'license': 'MIT', 'n_tokens_mistral': 15626, 'n_tokens_neox': 16087, 'n_words': 3923, 'path': 'lab1-2/notebook.ipynb', 'repo_name': 'semka95/decision-theory', 'size': '36057'}