I have a query in solving the problem below:

An automobile company has two factories. One factory has 400 cars (of a certain model) in stock and the other factory has 300 cars (of the model) in stock. Two customers order this car model. The first customer needs 200 cars, and the second customer needs 300 cars. The cost of shipping cars from the two factories to the customers is shown:

Customer 1 Customer 2
Factory 1 \$ 30 \$ 25
Factory 2 \$ 36 \$ 30

How should the company ship the cars in order to minimize the shipping cost?

I am confused about how to proceed with this problem. I have considered the slack variables $x_3$ through $x_6$, and conversion of the minimisation problem to a maximisation one, and got:

$\text{Maximise Z}=6x_1+5x_2-16200$
$\text{subject to, }x_1+x_2+x_3=400$
$~~~~~~~~~~~~~~~~~~~x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$

However, when I start with the dual simplex method, I cannot get an entering variable, since the $C_j-Z_j$ values of the first iteration are all $\gt 0$.
How do I solve this using simplex and/or dual simplex? Any help is appreciated.


You first need to transform this into normal form. Depending on how you learned it, you need to transform all constraints to the form $a\ge b$, or $a\le b$, where in $a$ you have variables and in $b$ only constants.

Transform $=$ into $\le$ and $\ge$ and from there you can easily transform this into normal form

  • $\begingroup$ I have already converted all constraints into $\le$ form and have added the slack variables. What I have written in the question is simply the set of equations I have got after performing preliminary calculations on the original LPP $\endgroup$
    – Jayajit
    May 26 at 14:06
  • $\begingroup$ Can you elaborate a bit more on the algorithm you are using? $\endgroup$
    – nir shahar
    May 26 at 18:16
  • $\begingroup$ I am using the dual simplex method as explained in this video: youtube.com/watch?v=DrcEdYebchw $\endgroup$
    – Jayajit
    Jun 9 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.