/**
* THUẬT TOÁN ĐƠN ÁNH ĐỐI NGỮA + ÉP NGHIỆM NGUYÊN TỐI ƯU (MIP HEURISTIC)
* Giải bài toán cắt cuộn 1D & xuất Báo cáo chuẩn xác 73 cuộn ra Google Sheets.
*/
function solveCuttingStockAndExportToSheet() {
const ROLL_WIDTH = 5600; // Chiều rộng cuộn mẹ (mm)
// 1. KHAI BÁO DỮ LIỆU BÀI TOÁN
const items = [
{ width: 1380, demand: 22 },
{ width: 1520, demand: 25 },
{ width: 1560, demand: 12 },
{ width: 1710, demand: 14 },
{ width: 1820, demand: 18 },
{ width: 1880, demand: 18 },
{ width: 1930, demand: 20 },
{ width: 2000, demand: 10 },
{ width: 2050, demand: 12 },
{ width: 2100, demand: 14 },
{ width: 2140, demand: 16 },
{ width: 2150, demand: 18 },
{ width: 2200, demand: 20 }
];
const widths = items.map(it => it.width);
const demands = items.map(it => it.demand);
const M = items.length;
// 2. SINH TẤT CẢ CÁC MẪU CẮT HỢP LỆ (PATTERN GENERATION)
const patterns = [];
function generatePatterns(idx, currentPattern, currentWidth) {
if (idx === M) {
if (currentWidth > 0) patterns.push([...currentPattern]);
return;
}
const maxCount = Math.floor((ROLL_WIDTH - currentWidth) / widths[idx]);
for (let count = maxCount; count >= 0; count--) {
currentPattern.push(count);
generatePatterns(idx + 1, currentPattern, currentWidth + count * widths[idx]);
currentPattern.pop();
}
}
generatePatterns(0, [], 0);
const N = patterns.length;
// 3. THIẾT LẬP BẢNG ĐƠN ÁNH ĐỐI NGỮA (DUAL SIMPLEX TABLEAU)
const numCols = M + N + 1;
const numRows = N + 1;
let T = Array.from({ length: numRows }, () => new Array(numCols).fill(0));
for (let j = 0; j < N; j++) {
for (let i = 0; i < M; i++) T[j][i] = patterns[j][i];
T[j][M + j] = 1;
T[j][numCols - 1] = 1;
}
for (let i = 0; i < M; i++) T[N][i] = -demands[i];
const EPS = 1e-9;
// 4. GIẢI BÀI TOÁN BẰNG ĐƠN ÁNH 1 PHA (STANDARD SIMPLEX)
while (true) {
let p = -1, minVal = -EPS;
for (let c = 0; c < M + N; c++) {
if (T[N][c] < minVal) { minVal = T[N][c]; p = c; }
}
if (p === -1) break; // Đã tìm thấy nghiệm tối ưu
let q = -1, minRatio = Infinity;
for (let r = 0; r < N; r++) {
if (T[r][p] > EPS) {
const ratio = T[r][numCols - 1] / T[r][p];
if (ratio < minRatio) { minRatio = ratio; q = r; }
}
}
if (q === -1) {
SpreadsheetApp.getUi().alert("Bài toán không giới hạn (Unbounded).");
return;
}
const pivotVal = T[q][p];
for (let c = 0; c < numCols; c++) T[q][c] /= pivotVal;
for (let r = 0; r < numRows; r++) {
if (r !== q) {
const factor = T[r][p];
if (Math.abs(factor) > EPS) {
for (let c = 0; c < numCols; c++) T[r][c] -= factor * T[q][c];
}
}
}
}
// 5. LỌC NGHIỆM VÀ ÉP NGUYÊN THÔNG MINH (MIP HEURISTIC ROUNDING)
const totalRollsFloat = T[N][numCols - 1]; // ~72.917
const targetTotalRolls = Math.ceil(totalRollsFloat - EPS); // Chuẩn 73 cuộn
let rawSelected = [];
for (let j = 0; j < N; j++) {
const x_j = T[N][M + j];
if (x_j > EPS) {
// Khử sai số dấu phẩy động
const cleanVal = Math.abs(x_j - Math.round(x_j)) < 1e-5 ? Math.round(x_j) : x_j;
const intVal = Math.floor(cleanVal);
const frac = cleanVal - intVal;
rawSelected.push({ index: j, val: cleanVal, intVal: intVal, frac: frac, pattern: patterns[j] });
}
}
// Tính số cuộn cần phân bổ thêm để tổng đạt đúng targetTotalRolls (73 cuộn)
let currentTotal = rawSelected.reduce((sum, item) => sum + item.intVal, 0);
let deficit = targetTotalRolls - currentTotal;
// Sắp xếp các mẫu theo phần thập phân giảm dần để ưu tiên cộng thêm 1 cuộn
rawSelected.sort((a, b) => b.frac - a.frac);
for (let i = 0; i < rawSelected.length; i++) {
if (deficit > 0 && rawSelected[i].frac > EPS) {
rawSelected[i].intVal += 1;
deficit--;
}
}
// Sắp xếp lại theo thứ tự Mẫu số ban đầu
rawSelected.sort((a, b) => a.index - b.index);
// 6. TẠO HOẶC LẤY SHEET "BÁO CÁO TỐI ƯU CẮT CUỘN"
const ss = SpreadsheetApp.getActiveSpreadsheet();
const sheetName = "Báo Cáo Tối Ưu Cắt Cuộn";
let sheet = ss.getSheetByName(sheetName);
if (!sheet) {
sheet = ss.insertSheet(sheetName);
} else {
sheet.clear(); // Xóa sạch dữ liệu cũ
}
sheet.setHiddenGridlines(false);
// 7. TRÌNH BÀY BẢNG BÁO CÁO DỮ LIỆU
const startRow = 10;
const headers = [
"STT", "Mẫu số", "Số cuộn áp dụng (Thực)", "Số cuộn làm tròn", "Chi tiết sơ đồ cắt", "Thừa (mm/cuộn)", "Tổng phế liệu (mm)"
];
let tableData = [];
let patternCount = 1;
let totalSystemWaste = 0;
let totalRoundedRolls = 0;
rawSelected.forEach(item => {
if (item.intVal > 0) {
const p = item.pattern;
const usedWidth = p.reduce((sum, cnt, k) => sum + cnt * widths[k], 0);
const wastePerRoll = ROLL_WIDTH - usedWidth;
const patternTotalWaste = wastePerRoll * item.intVal;
totalRoundedRolls += item.intVal;
totalSystemWaste += patternTotalWaste;
const cutsStr = p
.map((cnt, k) => cnt > 0 ? `${cnt} cuộn [${widths[k]}mm]` : null)
.filter(Boolean)
.join(" + ");
tableData.push([
patternCount++,
`Mẫu ${item.index + 1}`,
Number(item.val.toFixed(3)),
item.intVal, // Đã ép nguyên tối ưu (Tổng = 73)
cutsStr,
wastePerRoll,
patternTotalWaste
]);
}
});
// 8. ĐỊNH DẠNG TIÊU ĐỀ & BẢNG THÔNG SỐ CHUNG
sheet.getRange("A1:G1").merge().setValue("BÁO CÁO TỐI ƯU KẾ HOẠCH CẮT CUỘN (SIMPLEX)")
.setFontWeight("bold").setFontSize(16).setHorizontalAlignment("center")
.setBackground("#1a73e8").setFontColor("#ffffff");
sheet.getRange("A3:B3").merge().setValue("THÔNG SỐ TỔNG QUAN").setFontWeight("bold").setBackground("#e8f0fe");
sheet.getRange("A4").setValue("Kích thước cuộn mẹ:"); sheet.getRange("B4").setValue(`${ROLL_WIDTH} mm`);
sheet.getRange("A5").setValue("Tổng số mẫu cắt hợp lệ sinh ra:"); sheet.getRange("B5").setValue(`${N} mẫu`);
sheet.getRange("A6").setValue("Tổng số cuộn mẹ cần dùng (Số thực LP):"); sheet.getRange("B6").setValue(totalRollsFloat.toFixed(3));
// Ghi tổng số cuộn thực tế chuẩn đét 73 cuộn
sheet.getRange("A7").setValue("TỔNG SỐ CUỘN MẸ THỰC TẾ (LÀM TRÒN):").setFontWeight("bold");
sheet.getRange("B7").setValue(`${totalRoundedRolls} CUỘN`).setFontWeight("bold").setFontColor("#d93025");
// 9. ĐẨY BẢNG CHI TIẾT VÀ ĐỊNH DẠNG
sheet.getRange(startRow, 1, 1, headers.length).setValues([headers])
.setFontWeight("bold").setBackground("#34a853").setFontColor("#ffffff")
.setHorizontalAlignment("center");
if (tableData.length > 0) {
sheet.getRange(startRow + 1, 1, tableData.length, headers.length).setValues(tableData);
// Kẻ viền bảng
const dataRange = sheet.getRange(startRow + 1, 1, tableData.length, headers.length);
dataRange.setBorder(true, true, true, true, true, true, "#cccccc", SpreadsheetApp.BorderStyle.SOLID);
// Căn lề
sheet.getRange(startRow + 1, 1, tableData.length, 4).setHorizontalAlignment("center");
sheet.getRange(startRow + 1, 6, tableData.length, 2).setHorizontalAlignment("right");
// Hàng tổng kết phế liệu
const lastRow = startRow + tableData.length + 1;
sheet.getRange(lastRow, 1, 1, 6).merge().setValue("TỔNG LƯỢNG GIẤY/NHÔM THỪA TOÀN HỆ THỐNG:")
.setFontWeight("bold").setHorizontalAlignment("right");
sheet.getRange(lastRow, 7).setValue(`${totalSystemWaste} mm`)
.setFontWeight("bold").setFontColor("#d93025");
}
// Tự động căn chỉnh độ rộng các cột
for (let col = 1; col <= headers.length; col++) {
sheet.autoResizeColumn(col);
}
// Thông báo trên giao diện Google Sheets
SpreadsheetApp.getUi().alert(`✅ Đã giải xong bài toán!\nTỔNG SỐ CUỘN MẸ THỰC TẾ CẦN DÙNG: ${totalRoundedRolls} CUỘN.\nKết quả xuất tại tab "${sheetName}".`);
}
..
