Hand-in exercise 1 in Linear and Combinatorial Optimization, 2008.

Do exercises 1, 2, 3 and 4 below. Hand-in a solution by sending (i) the matlab file for the function checkbasic1.m and (ii) the simplex tableaux for exercises 2 and 3 and (iii) answers to exercise 4 to Klas Josephson, (klasj@maths.lth.se).

Due date: 30 January 2008.

1. Construct a MATLAB-script checkbasic1.m

function [tableau,x,basic,feasible,optimal]=checkbasic1(A,b,c,basicvars);
% [x,basic,optimal,feasible]=checkbasic1(A,b,c,basicvars),
% INPUT: A - mxn matrix
%        b - mx1 matrix
%        c - nx1 matrix
%        basicvars - list of m indices between 1 and n.
% OUTPUT
%        tableau  - the (m+1) x (n+1) matrix representing the simplex tableau
%                   (skip the column corresponding to the objective function z)
%        x        - nx1 matrix. The basic solution corresponding
%                   to basic variables basicvars.
%        basic    - 1 if x is a basic solution
%        optimal  - 1 if x is an optimal solution
%        feasible - 1 if x is a feasible solution
% to the LP-problem in canonical form
%  max z = c'*x
%  subject to A*x=b, x>=0

2. Test the script on the following data. Compare the tableau
you obtain with the ones in the book. 

% Script for testing the tableau.
A = [2 2 1 0;5 3 0 1];
b = [8;15];
c = [120;100;0;0];

basicvars=[3 4];
[tableau,x,basic,feasible,optimal]=checkbasic1(A,b,c,basicvars);
disp('This should give Tableau 2.1 in the book');
tableau

basicvars=[3 1];
[tableau,x,basic,feasible,optimal]=checkbasic1(A,b,c,basicvars);
disp('This should give Tableau 2.3 in the book');
tableau

basicvars=[2 1];
[tableau,x,basic,feasible,optimal]=checkbasic1(A,b,c,basicvars);
disp('This should give Tableau 2.4 in the book');
tableau

A=[1 2 2 1 1 0 1 0 0; 1 2 1 1 2 1 0 1 0;3 6 2 1 3 0 0 0 1];
b=[12;18;24];
c=[0; 0; 0; 0; 0; 0; -1; -1; -1];

basicvars=[7 8 9];
[tableau,x,basic,feasible,optimal]=checkbasic1(A,b,c,basicvars);
disp('This should give Tableau 2.25 in the book');
tableau

basicvars=[3 6 2];
[tableau,x,basic,feasible,optimal]=checkbasic1(A,b,c,basicvars);
disp('This should give Tableau 2.28 in the book');
tableau

% Change to the original problem
A=[1 2 2 1 1 0; 1 2 1 1 2 1 ;3 6 2 1 3 0 ];
c=[1;-2;-3;-1;-1;2];

basicvars=[3 6 2];
[tableau,x,basic,feasible,optimal]=checkbasic1(A,b,c,basicvars);
disp('This should give Tableau 2.29 in the book');
tableau

basicvars=[3 6 1];
[tableau,x,basic,feasible,optimal]=checkbasic1(A,b,c,basicvars);
disp('This should give Tableau 2.30 in the book');
tableau

3. Solve the following linear programming problem in canonical form using manual Simplex steps based on your checkbasic1.m

A=[2,-3,2,1,0;-1,1,1,0,1];
b=[3;5];
c=[3;2;1;0;0];

4. Determine the number of basic solutions and basic feasible solutions for the following LP-problem.

A=[1,2,1,0;1,2,0,1];
b=[4;7];
c=[1;-1;0;0];