# How-to solve a transportation problem with the Simplex algorithm in Maple

Posted

Consider the following transportation problem. Here you have your costs, supplies and demands.

 1 2 3 4 Supply 1 464 513 654 867 75 2 352 416 690 791 125 3 995 682 388 685 100 Demand 80 68 70 85

Now, the trick is to formulate it as a LP-problem.

Setting it up

restart:
with(simplex):
with(ArrayTools):
with(linalg):


The objective function

First, we need to formulate an objective function. This is done by using all the cost variables from the table above. The variable C is a vector that contains all the costs. The X variable counts how many variable there are and the dotprod method generates our objective function. It is possible to do this differently but I think this makes it easier to understand.

If the problem involves a big M, just replace it with a very large number.

c := vector([
464,513,654,867,
352,416,690,791,
995,682,388,685
]);

x := vector(Size(c,2));
z := dotprod(x,c);


Creating the constrains

There are two types of constraints here. The first is for the supplies and the second is for the demand. I have added an empty line within the constraints just to make is easier to see. The supply constraints are made out each of the rows from the table and the demands are from the columns.

c := [
x[1] + x[2] + x[3] + x[4] = 75,
x[5] + x[6] + x[7] + x[8] = 125,
x[9] + x[10] + x[11] + x[12] = 100,

x[1] + x[5] + x[9] = 80,
x[2] + x[6] + x[10] = 65,
x[3] + x[7] + x[11] = 70,
x[4] + x[8] + x[12] = 85
];


Using the simplex method

minimize(z, c, NONNEGATIVE);

assign(%); Z;


# How-to solve a LP problem in Maple with the Simplex algorithm

Posted

Linear programming (LP) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.

One way to solve LP-problem is to use the Simplex algorithm, which guarantees to find the global optimum (if certain precautions against cycling are taken). I’m not going to explain the Simplex algorithm here, so I will assume that you have that covered.

You could solve the problem by hand, but this takes time. You could also use Excel to solve the problem which is nice because Excel can also give you some insights about the model. A third option is to use Maple (which is why you are reading this).

I have choosen to name the unknown variable like this x[1] but it could just as well have been x1.

Setting it up

restart:
with(simplex):


The objective function

Z := 6*x[1] + 8*x[2] + 7*x[3] + 6*x[4];


Creating the constrains

c := [
3*x[1] + 4*x[2] + 5*x[3] + 4*x[4] >= 36,
5*x[1] + 8*x[2] + 4*x[3] + 3*x[4] >= 48,
x[1] +   x[2] +   x[3] +   x[4] <= 12,
x[1]                            >= 3,
x[2]                   >= 3,
x[3]          >= 3,
x[4] >= 3
];


Using the simplex method

minimize(Z,c, NONNEGATIVE);

assign(%); Z;


If you want to maximize instead, you should replace it with the method Maximize. You also might want to call restart after calling the assign method.

Maple can’t generate a sensitivity analysis like Excel, so you will still need to do this yourself.

# The Startup Owner’s Manual by Steve Blank and Bob Dorf

Posted

Having started a few companies over the years, I wish this book had been available a long time ago. The book describes a very good framework on how to getting things moving. The book takes to through the different phases of a startup. One of the things I really like about this book is the fact that it makes use of Alexander Osterwalder’s “Business Model Canvas”. The book fully integrates Osterwalder’s framework into this books own model.

The first rule of the book is “There are no facts inside your building”. The rule might seem logical but I often see entrepreneurs who have not spoken with a single customer and are already building their product. Go out and interview the customers. Find out what they want. You can’t build a great product based on (wrong) assumptions.

Rule No. 6 of the Customer Development Manifesto also says: Design Experiments and Test to Validate Hypotheses. Essentially, you create an experiment to validate your product or target market. In doing so, you’ll learn how to make your product better or where to pivot.

These are just a few examples of what’s not talked about in other books. If you want to be an entrepreneur this is a must read.

# Business Model Generation by Alexander Osterwalder

Posted

The first thing that strikes me is that this book is very different from other business books. The writing is accessible, and it may be that many of the concepts are more easily absorbed here than in the original source materials and it is beautifully laid out.

The book focuses on ways to think about a business model. It contains nine building blocks that can go into your model.

• Customer segments
• Value proposition
• Channels
• Customer Relationships
• Revenue streams
• Activities
• Resources
• Partners
• Cost Structure

These building blocks are laid out on a page that is referred to as a “business model canvas”. The business model canvas can be used to describe a wide variety of business models.

A major section on strategy includes a section on how to evaluate existing business models, identifying problems, and brainstorming about possible solutions. When you read this section you can help to think about Porter’s 5 Forces, because there are some similarities.

Overall the book provides you with a good systematic framework, which can help you to analyze and compare business models. I will recommend to everyone who has a interest in business models.

# How great leaders inspire action by Simon Sinek

Posted

Here is how Apple actually communicates: Why? Everything we do we believe in challenging the status quo. We believe in thinking differently. How? The way we challenge status quo is by making our products beautifully designed simple to use, and user friendly. What? We just happen to make great computers. Want to buy one?

- Simon Sinek

See Simon Sinek TED Talk

# Free: How Today’s Smartest Businesses Profit by Giving Something for Nothing by Chris Anderson

Posted

The book is a good introduction to the various strategies for making money from giving away a free product. This can be great if you’re trying to start a business and need some ideas.

The ongoing drop in the cost of bandwidth, storage and computer processing power, which brings the cost of each of these digital age services to almost zero, “free” is becoming the standard way of pricing various web services. This means that the business people and others who wishes to profit from “free”, has to figure out the trick to sell services or products related to the free one.

As a customer, there is a huge difference between what is free and what is cheap. The concept of Free is important because the majority of company’s today strive in an environment where raising demand for one thing, is gained by giving a complimentary item away for free.

I enjoyed this book, and it helped me see possibilities for a new economy in the digital age. Overall, this is an interesting book that takes a look at modern economy.

# Bridge crossing (Microsoft Hiring test)

Posted

A good friend of mine send me this quiz which was found in compendium at her university. The course was about Mathematical Programming. I have copied the quiz directly.

The assignments:

Warning, this assignment is rather hard. It should have been used in a Microsoft during hiring interviews.

Four persons have to cross a bridge. The times each needs to cross it are:

• 5 min
• 10 min
• 20 min
• 25 min.

It is dark and they only have one lamp, we have the following constraints:

• the bridge can only be crossed if one has a lamp, while it is too dark.
• 2 persons at most are allowed to be on the bridge at the same time.
• the speed of a pair is determined by the speed of the slower person.
• the lamp can last only an hour.
• the lamp cannot be thrown.

Can you figure out a way so that the four men can cross the bridge in 60 minutes.

Solution

Here is how I solved it. It is a classical problem where you need to move back and forth a couple of times.

Crossing time for each person

A – 5 minutes.
B – 10 minutes.
C – 20 minutes.
D – 25 minutes.

The plan is as the following

Time Start Movement End
0 minutes A B C D
10 minutes C D A & B walks over A B
15 minutes A C D A walks back B
40 minutes A C & D walks over B C D
50 minutes A B B walks back C D
60 minutes A & B walks over A B C D

Done.

Posted

Recently someone asked me if it was possible to track outbound links on his website with Google Analytics.

Here is a working solutions. Note that you might have to wait 24 hours before it will show up under Events.

It is not a bullet since it depends Google Analytics to registre the event fast enough. You can always tweak the setTimeout value.

$(document).ready(function() {$("a").on('click',function(e){
var url = \$(this).attr("href");
if (e.currentTarget.host != window.location.host) {
_gaq.push(['_trackEvent', 'Outbound Links', e.currentTarget.host, url, 0]);
if (e.metaKey || e.ctrlKey) {
var newtab = true;
}
if (!newtab) {
e.preventDefault();
setTimeout('document.location = "' + url + '"', 200);
}
}
});
});


# Problem when uninstalling ASP.NET Web Pages

Posted

I had just recently installed Service Pack 1 for Visual Studio 2010, which broke the Intellisense in the Razor ViewEngine. A quick search on Google showed that other people has had the same issue. For me it came down to uninstalling ASP.NET Web Pages (and ASP.NET MVC). For some reason that turned out to be difficult.

The Event Viewer showed the following error message.

”Error 1722. There is a problem with this Windows Installer package. A program run as part of the setup did not finish as expected. Contact your support personnel or package vendor.”

Application: WebConfigCA.exe
Framework Version: v4.0.30319
Description: The process was terminated due to an unhandled exception.
Exception Info: System.ArgumentException
Stack:
at System.Web.Configuration.VirtualDirectoryMapping..ctor(System.Web.VirtualPath, System.String, Boolean, System.String)
at System.Web.Configuration.VirtualDirectoryMapping..ctor(System.String, Boolean)
at WebConfigCA.Program.GetWebConfig(System.String)
at WebConfigCA.Program.Main(System.String[])

A few people around the web suggested the following solution:

1. Remove the trailing backslash from the following registry keys:

HKEY_LOCAL_MACHINESOFTWAREMicrosoftASP.NET4.0.30319.0Path
HKEY_LOCAL_MACHINESOFTWAREWow6432NodeMicrosoftASP.NET4.0.30319.0Path

2. Uninstalled the old version of “Microsoft ASP.NET Web Pages”.

3. Add the trailing backslash back to those keys.

This did not work for me.

My Solution

So I fired up ILSpy and opened up WebConfigCA.exe, just to get an idea about why it had thrown an exception. Nothing really stood out, so I created a Console Application Project in Visual Studio and pasted the code. I added the needed references and ran it (when testing, remember elevated permissions) – No exception got thrown. I thought to myself that was strange, so I toke my newly created console app and replaced it with WebConfigCA.exe (It might be a good idea to keep a backup). I ran the uninstaller again and this time it ran fine and I finally got ASP.NET Web Pages uninstalled.

By going through the code again, I see that I did add a line of code (which I did just to test it in VS but forgot to remove, not sure if that was the real trick, but don’t think so).

Anyway, here it is.

args = new string[1]{"-U"};