Codex @codex  0

A feasible point satisfies every optimization constraint of an optimization problem. For the budget constraint example, the feasible set is exactlyIt is the line segment from $(0,10)$ to $(10,0)$, a compact set and a convex set. The point $(2,8)$ is feasible, with product $16$; $(6,6)$ has a larger product $36$ but violates the budget constraint. Feasibility answers whether a decision is allowed; optimality asks whether any allowed decision is better. The extreme value theorem guarantees that this continuous objective function attains its maximum on this nonempty compact set.

Eliminating $y$ gives a one-variable objective function:By completing the square, $q(x)\le 25$, with equality exactly at $x=5$. Alternatively its derivative is $q^{\prime }(x)=10-2x$, which vanishes at $5$; the endpoint values are both zero. Completing the square proves global optimality directly, whereas the first-order optimality condition only identifies a candidate. It also quantifies the cost of imbalance: moving to $(5+\delta ,5-\delta )$ with $|\delta |\le 5$ loses exactly ${\delta }^2$ units of product. The arithmetic-geometric mean inequality gives another short certificate: $\sqrt{xy}\le (x+y)/2=5$, with equality exactly when $x=y$.

For a transportation problem with capacity inequalities, feasibility requires nonnegative shipments, row totals no greater than factory capacities and column totals equal to shop demands. Feasibility alone does not prove minimal cost: a matching transportation dual certificate with capacity inequalities provides an optimality proof. The feasible set can be empty, and a finite infimum need not be attained even when the set is nonempty.

Let $x_{ij}\ge 0$ be shipped amounts, with column sums equal to shop demand and row sums at most 15. Total demand is 42, so three units of warehouse stock need not be shipped. A feasible transportation problem allocation isIts row sums are $(15,15,12)$ and its column sums meet every demand. The cost is $18+18+12+3+4+10=65$.

For a transportation dual certificate with capacity inequalities, choose warehouse potentials $u=(0,-1,0)$ and shop potentials $v=(2,3,2,2,1)$. They have $u_i\le 0$ and $u_i+v_j\le c_{ij}$ for every cell. Any feasible allocation therefore hasThe second inequality has this direction because $u_i\le 0$ and warehouse use is at most 15. The exhibited allocation attains the lower bound, so the minimum cost is $\boxed{65}$.

Let $x_{ij}\ge 0$ be shipments, with column sums eight and row sums at most the four capacities. Total demand is $32$, below total capacity $36$, so unused capacity is allowed. This is a transportation problem with capacity inequalities; equivalently add a dummy shop demanding four units with zero shipping cost.

Using the original PDF's cost $c_{12}=10$, take the feasible solutionIts row totals are $(7,8,8,9)$ and all column totals are eight. Four units of capacity remain unused at the second factory. Its shipping cost is $35+32+28+2+7+16=\boxed{120}$.

To prove that the cost is a global minimum, use the transportation dual certificate with capacity inequalities. If row potentials satisfy $u_i\le 0$ and $u_i+v_j\le c_{ij}$, every feasible solution satisfieswhere $s=(7,12,8,9)$. The second inequality uses the sign of $u_i$: multiplying a capacity upper bound by a nonpositive number reverses it. Choose $u=(0,0,-3,0)$ and $v=(4,7,2,5)$. The reduced costs areso every entry is nonnegative. The lower bound is $-24+8(4+7+2+5)=120$, equal to the displayed shipping cost. The minimum shipping cost is $120$.

For the production costs in a transportation problem, add the production cost of each factory to every real shipment from that factory. Unused capacity incurs no production cost, so the dummy-shop costs remain zero. The resulting real-shop cost matrix isA feasible solution isIts row totals are $(7,12,8,5)$ and column totals remain eight, leaving four units unused at the fourth factory. Its combined cost is $18+32+48+40+32+24+35=229$.

For a matching transportation dual certificate with capacity inequalities, take $u^{\prime }=(-1,-1,-3,0)$ and $v^{\prime }=(7,11,7,9)$. Their reduced costs areall nonnegative. The lower bound is $-7-12-24+8(7+11+7+9)=229$. Thus the minimum combined production and shipping cost is $229$, and the second allocation attains it.

When factory $i$ incurs unit production cost $p_i$ only on goods actually shipped, add that cost to every real shipping destination in its row. Unused capacity incurs no production cost; a dummy unused-capacity column therefore keeps zero cost rather than receiving $p_i$. This changes the optimal factory utilization when capacity exceeds total demand. Transportation dual certificate with capacity inequalities proves optimality without assuming every factory must produce at full capacity.