In my course of linear programming, we are given the following definitions of a primal/dual model. However, I cannot really get my head around what it actually is? Are we simplifying the problem? Are we making it better to work with?

Here are the following definitional models: $$\text{Primal Model}$$ $$ \begin{align} \max & \sum_{j=1}^nb_jy_j \\ \text{s.t.} &\sum_{j=1}^n a_{ij}x_i = b_i &1\leq i \leq m\\ &x_j \geq 0 &1\leq j \leq n \end{align} $$


$$\text{Dual of Primal}$$ $$ \begin{align} \min & \sum_{i=1}^mb_iy_i \\ \text{s.t.} &\sum_{i=1}^m a_{ij}y_i \geq c_j &1\leq j \leq n\\ &y_i \in \mathbb{R} &1\leq i\leq m \end{align} $$


1 Answer 1


Let’s think of it in a different light:

Suppose we are shopping for candy bar, but we want to minimize how much we want to spend for a candy bar at the store. Our personal model is a minimization of which saves us the most money shopping for this candy bar. Likewise, suppose we are the owner of the store that this customer is shopping at for a candy bar. We want to maximize the amount of profit made for selling a candy bar. Thus, as a shop owner, our model would involve maximizing the amount of profit made. These proposed models in this scenario are duals of each other, and will actually provide the same objective function output of one another.

Fast food restaurants do this too when they are trying to plan on locations that compete against their competitors, thus this is why they place their locations right next to one-another.

We sometimes take the dual of a model with a lot of variables and few constraints as it would simplify the amount of computations needed drastically. Suppose we had a model with $1000$+ variables, but one constraint, by taking its dual we can actually solve it with one pivot! So yes, it’s a way to simplify some difficult models.

Since we usually only care about the objective function outputs of dual models, it would be wise to look into the following subjects:

In addition, to visualize what each objective function is doing, look into a Duality Gap in which we can graph the behaviors of a Primal and Dual:

enter image description here

This above image was taken from here.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .