O’zbekiston respublikasi axborot texnoloogiyalari va kommunikatsiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnoloogiyalari universiteti muammo, tahlil va yechim fani bo’yicha laboratoriya ishi-2

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOOGIYALARI VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD
AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOOGIYALARI UNIVERSITETI

Muammo, tahlil va yechim fani bo’yicha
LABORATORIYA ISHI-2

Mavzu: Maqsadni aniqlash masalasi. Taqsimlash masalasini yechish dasturini yaratish.

Guruh: 030-19
Bajardi : Boynazarov Jalil
Tekshirdi : XO‘JAKULOV T. A.

TOSHKENT-20223

Ishdan maqsad: Taqsimlash masalasini yechish dasturini yaratish.
Nazari qism: Harakat loyihasining barcha individual qisimlari maqsad va vazifalar bilan to‘liq tafsiflanib, vaqt chegaralari belgilanidan so‘ng qaysi ishni kim bajarishini taqsimlash vaqti keldi. Bu ish yaxshi menedjer yoki gruppa rahbari yuklanadi. Ish imkon darajasida teng taqsimlanishi lozim. Guruh qatnashchilari o‘z sohasida kuch sarflashi lozim. Men bor fikrlarimning barchasidan foydalana olmayman, chunki ular meniki emas(Vudrov Vilson AQSh prezidenti). Yangi xodim sifatida Siz o‘zingiz istagan ish o‘rnini ola olmaysiz. Siz bu xoxlagan ish o‘rningizni ishlab olishingiz lozim. Siz qanday bo‘lishidan qatiy nazar nima sizga berilgan topshiriqlarni bajaring. Har safar yanada yaxshi bajaring. Agar siz o‘z istagingiz bilan vazifa olsangiz maftunkorroq yoki onsonroq ishlarni berishlarini so‘ramang. Har kim nega siz bunga qo‘l urayotganingizni biladi va hamkasblaringiz buni yoqlashmaydi. Buning o‘rniga siz berilaytgan vaziani uddalay olishningiz mumkinligini biling. Vazifaga 36 qo‘shilganlar bilan samarali bog‘lanib o‘z kuchingiz va zaif tomonlaringizni so‘rang. Hech kim hohlamagan ishlarni so‘rang.
Amaliy qism: Bu masalani yechishda java dasturlash tilidan foydalandim.
import java.util.Arrays;

public class DistributionProblemSolver {

public static int[][] solveDistributionProblem(int[][] costMatrix) {
int numRows = costMatrix.length;
int numCols = costMatrix[0].length;

// Step 1: Subtract the smallest value from each row

for (int i = 0; i < numRows; i++) {
int minRowValue = Arrays.stream(costMatrix[i]).min().getAsInt();
for (int j = 0; j < numCols; j++) {
costMatrix[i][j] -= minRowValue;
}
}

// Step 2: Subtract the smallest value from each column

for (int j = 0; j < numCols; j++) {
int[] column = new int[numRows];
for (int i = 0; i < numRows; i++) {
column[i] = costMatrix[i][j];
}
int minColValue = Arrays.stream(column).min().getAsInt();
for (int i = 0; i < numRows; i++) {
costMatrix[i][j] -= minColValue;
}
}

// Step 3: Allocate the goods to distribution centers

int[] assignment = new int[numRows];
Arrays.fill(assignment, -1);
boolean[] rowUsed = new boolean[numRows];
boolean[] colUsed = new boolean[numCols];

for (int i = 0; i < numRows; i++) {

for (int j = 0; j < numCols; j++) {
if (costMatrix[i][j] == 0 && !colUsed[j] && !rowUsed[i]) {
assignment[i] = j;
colUsed[j] = true;
rowUsed[i] = true;
break;
}
}
}

// Step 4: Improve the allocation using recursion

boolean[] visited = new boolean[numCols];
improveAllocation(costMatrix, assignment, visited);

return costMatrix;

}

private static boolean improveAllocation(int[][] costMatrix, int[] assignment, boolean[] visited) {

int numRows = costMatrix.length;
int numCols = costMatrix[0].length;

for (int i = 0; i < numRows; i++) {

if (visited[i]) {
continue;
}
visited[i] = true;

for (int j = 0; j < numCols; j++) {

if (costMatrix[i][j] == 0) {
if (assignment[i] == -1 || improveAllocation(costMatrix, assignment, visited)) {
assignment[i] = j;
return true;
}
}
}
}

return false;

}

public static void main(String[] args) {

int[][] costMatrix = {
{3, 6, 1},
{2, 4, 5},
{7, 8, 9}
};

int[][] allocation = solveDistributionProblem(costMatrix);

System.out.println("Optimal Allocation:");
for (int i = 0; i < allocation.length; i++) {
System.out.println("Goods " + i + " allocated to Distribution Center " + allocation[i][0]);
}
}
}