Model Transportasi dengan Metode Northwest Corner


Dalam permasalahan model transportasi pada Program Linier, ada banyak cara yang dapat digunakan untuk menemukan solusi, salah satunya dengan metode Northwest Corner. Metode ini merupakan metode untuk menentukan solusi awal yang pengalokasiannya berawal dari pojok kiri atas (Barat Laut/North West) hingga ke pojok kanan bawah (Tenggara/South East). Selanjutnya, pengalokasian dilakukan pada kotak X[i,j+1] bila permintaan di kolom j telah terpenuhi dan pada kotak X[i+1,j] bila permintaan di baris i telah terpenuhi.


Sebagai contoh, kita perhatikan tabel di bawah ini:


Langkah-langkah pengerjaan dengan metode North-West Corner: (sumber: Tjutju Tarliah Dimyati-Ahmad Dimyati, “OPERATION RESEARCH, Model-model Pengambilan Keputusan”, Sinar Baru Algensindo, 2003)

  1. Tampilkan persoalan dalam matriks.
  2. Selalu memulai pengisian yang pertama kali pada jalur yang berada pada pojok kiri atas. Pengisian atau pengalokasian barang pada jalur ini harus berpedoman kepada kapasitas yang ada dan jumlah permintaan yang harus dipenuhi.
  3. Lakukan gerakan zig-zag dari pojok kiri atas ke arah kanan bawah, sampai semua barang yang diproduksi habis terdistribusi dan memenuhi semua permintaan yang ada.
  4. Hitung total biaya yang diperoleh.

Pada persoalan di atas, kita mulai dari pojok kiri atas yaitu Kotak AP. Untuk kotak ini nilai Supply-nya adalah 5000 dan untuk Demand-nya adalah 6000. Kita pilih yang bernilai 5000 (minimum antara supplu dan demand). Selanjutnya, karena permintaan di P belum terpenuhi dan alokasi dari A sudah habis, kita bergerak ke bawah yaitu Kotak BP. Nilai Supply untuk kotak ini adalah 6000 dan Demand-nya adalah 1000 (6000-5000). Kemudian, yang kita pilih adalah 1000. Sekarang, permintaan di P sudah terpenuhi jadi kita bergerak ke kanan yaitu Kotak BQ. Nilai Supply dan Demand untuk kotak ini berturut-turut adalah 5000 (6000-1000) dan 4000. Kita pilih yang terkecil yaitu 4000. Permintaan di Q sudah terpenuhi dan alokasi dari B masih ada, jadi selanjutnya kita bergerak ke kanan ke Kotak BR. Supply dan Demand untuk kotak ini adalah 1000 (5000-4000) dan 2000. Nilai terkecilnya adalah 1000. Kondisi sekarang yaitu alokasi dari B sudah habis dan permintaan di R belum terpenuhi, maka gerakan selanjutnya adalah ke bawah yaitu Kotak CR. Nilai Supply dan Demand untuk kotak ini adalah 2500 dan 1000 (2000-1000). Kita pilih nilai 1000 sebagai nilai terkecil. Permintaan di R sudah terpenuhi dan alokasi dari C masih ada, sehingga kita bergerak ke kanan yaitu Kotak CS. Nilai Supply dan Demand-nya adalah 1500 (2500-1000) dan 1500. Karena keduanya sama, maka kita dapat memilih salah satu saja. Sekarang, permintaan di S sudah terpenuhi dan alokasi dari C juga sudah habis. Solusi terpecahkan!! Dan tabelnya menjadi seperti berikut:

 

Langkah selanjutnya adalah menghitung Total Biaya pengiriman:

 

Untuk menyelesaikan masalah di atas, saya telah membuat aplikasi sederhana menggunakan bahasa C. Berikut source codenya:

/*
	Nama File	: nwc.cpp
	Programmer	: Mohamad Tri Ramdhani
	NIM		: 0807645
	Tanggal dibuat	: 25 Mei 2011
*/

#include <stdio.h>
#include <conio.h>
#include <iostream.h>

int cost[10][10], alok[10][10];
int supp[10], demn[10];
int nsup, ndem, brs, kol, biaya, jsup, jdem;
int supply[10], demand[10];
int pil;

void input()
{
	int i,j;
	printf("Masukkan jumlah (max 10): \n");
	printf("Sumber (Supply) --> ");
	scanf("%d",&nsup);
	printf("Tujuan (Demand) --> ");
	scanf("%d",&ndem);
	if(ndem==0 || ndem>10 || nsup==0 || nsup>10) {
		printf("Jumlah Sumber dan Tujuan harus lebih dari 0 atau kurang dari atau sama dengan 10\n\n");
	}
	else
	{
		printf("\n-- Masukan nilai setiap sumber (supply) dan tujuan (demand) --\n");

		for(i=1;i<=nsup;i++){
			printf("Sumber %d = ",i);
			scanf("%d",&supp[i]);
			supply[i] = supp[i];
			jsup += supply[i];
		}

		for(j=1;j<=ndem;j++){
			printf("Tujuan %d = ",j);
			scanf("%d",&demn[j]);
			demand[j] = demn[j];
			jdem += demand[j];
		}

		if(jsup==jdem){
			printf("\n-- Masukan bobot tiap kotak --\n");
			for(i=1;i<=nsup;i++){
				for(j=1;j<=ndem;j++){
					printf("Kotak [%d,%d] = ",i,j);
					scanf("%d",&cost[i][j]);
				}
			}
		printf("\n\n");
		}else{
			printf("Jumlah supply tidak sama dengan jumlah demand, sehingga kasus ini tidak dapat diselesaikan\n\n");
		}
	}
}

void proses()
{
	int batas,i,j;
	batas = nsup+1;
	brs = 1;
	kol = 1;

	do {
		if(supp[brs] <= demn[kol]){
			alok[brs][kol] = supp[brs];
			demn[kol] -= alok[brs][kol];
			brs += 1;
		}else{
			alok[brs][kol] = demn[kol];
			supp[brs] -= alok[brs][kol];
			kol += 1;
		}
	}
	while (brs != batas);

	biaya = 0;
	for(i=1;i<=nsup;i++){
		for(j=1;j<=ndem;j++){
			biaya += (alok[i][j] * cost[i][j]);
		}
	}	

	printf("-- Tabel Bobot --\n");
	printf("\n\t\tTujuan");
    printf("\nSumber\t|");
    for (i=1;i<=ndem;i++)
    printf("  D%d\t|",i);
    printf(" Supply");
    for (j=1;j<=nsup;j++){
		printf("\n   S%d \t|",j);
		for(i=1; i<=ndem; i++)
		printf("  %d\t|",cost[j][i]);
		printf("  %d",supply[j]);
    }
    printf("\nDemand\t|");
    for(i=1; i<=ndem; i++)
    printf("  %d\t|",demand[i]);
    printf("\n\n\n");

    printf("-- Tabel Alokasi --\n");
	printf("\n\t\tTujuan");
    printf("\nSumber\t|");
    for (i=1;i<=ndem;i++)
    printf("  D%d\t|",i);
    printf(" Supply");
    for (j=1;j<=nsup;j++){
		printf("\n   S%d \t|",j);
		for(i=1; i<=ndem; i++)
		printf("  %d\t|",alok[j][i]);
		printf("  %d",supply[j]);
    }
    printf("\nDemand\t|");
    for(i=1; i<=ndem; i++)
    printf("  %d\t|",demand[i]);
    printf("\n\n");

    printf("\nTotal biaya optimal dengan metode Northwest Corner adalah %d \n\n",biaya);
	getch();
}

void main()
{
	do {
		printf("-- Menu Aplikasi NWC --");
		printf("\n1. Input data");
		printf("\n2. Tampilan hasil perhitungan");
		printf("\n3. Exit");
		printf("\n\nMasukan pilihan :");
		scanf("%d",&pil);
		switch(pil){
			case 1:input();break;
			case 2:proses();break;
		}
	}
	while(pil != 3);
	getch();
}

Untuk mendapatkan file source code di atas, silakan diunduh di sini.

About these ads

About Administrator

Aku lahir dari keluarga kecil yang bahagia. Aku anak bungsu dan laki-laki satu-satunya. Aku punya seorang kakak perempuan, sekarang dia uda kerja. Aku hingga kini masih kuliah di Program Studi Ilmu Komputer FPMIPA UPI, Bandung.

Posted on May 26, 2011, in Informasi, Inspirasi, Kuliah, Programming, Teknologi and tagged , , , , , , , , , , , , , , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,522 other followers

%d bloggers like this: