notes we can easily avoid this situationhoweverif we add special node with the supply/demand value br - now we have two optionsif (supply dominatesthen for each node with bi we add an arc (irwith infinite capacity and zero costotherwise (demand dominates)for each node with bi we add an arc (riwith the same properties now we have new network with siv{ }bi and it is easy to prove that this network has the same optimal value as the objective function consider the vertex as rubbish or scrap dump if the shops demand is less than what the warehouse suppliesthen we have to eject the useless goods as rubbish otherwisewe take the missing goods from the dump this would be considered shady in real lifeof coursebut for our purposes it is very convenient keep in mind thatin this casewe cannot say what exactly the "solutionof the corrected (with scrapproblem is and it is up to the reader how to classify the emergency uses of the "dump for examplewe can suggest that goods remain in the warehouses or some of the shop' demands remain unsatisfied even if we have we are not sure that the edge' capacities allow us to transfer enough flow from supply vertexes to demand ones to determine if the network has feasible flowwe want to find any transfer way what will satisfy all the problem' constraints of coursethis feasible solution is not necessarily optimalbut if it is absent we cannot solve the problem let us introduce source node and sink node for each node with bi we add source arc (sito with capacity bi and cost for each node with bi we add sink arc (itto with capacity -bi and cost figure maximum flow in the transformed network for simplicity we are ignoring the costs bi bj xij,uij - / / / - / / / / / / / / / - the new network is called transformed network nextwe solve maximum flow problem from to if the maximum flow saturates all the source and sink arcsthen the problem has feasible solutionotherwiseit is infeasible as for why this approach workswe'll leave its proof to the reader having found maximum flowwe can now remove sourcesinkand all adjacent arcs and obtain feasible flow in how do we detect whether the flow is optimal or notdoes this flow minimize costs of the objective function zwe usually verify "optimality conditionsfor the answer to these questionsbut let us put them on hold for moment and discuss some assumptions nowsuppose that we have network that has feasible solution does it have an optimal solutionif our network contains the negative cost cycle of infinite capacity then the objective lovely professional university