Giá thay đổi, khi nào vẫn giữ số máy tối ưu?
Chứng minh khoảng tỉ số chi phí giữ một lựa chọn nguyên tối ưu, xác định lúc đồng hạng và kiểm tra lại quyết định khi sản phẩm phải được làm trọn trên từng…
TOÁN THCS · ĐIỀU KIỆN TỐI ƯU VÀ GIẢ THIẾT MÔ HÌNH
Giá thay đổi, khi nào vẫn giữ số máy tối ưu?
Chứng minh khoảng tỉ số chi phí giữ một lựa chọn nguyên tối ưu, xác định lúc đồng hạng và kiểm tra lại quyết định khi sản phẩm phải được làm trọn trên từng máy.
1. Hỏi ngược: giá thay đổi bao nhiêu thì phải đổi quyết định?
Một lựa chọn rẻ nhất hôm nay có thể vẫn rẻ nhất khi đơn giá thay đổi. Thay vì chỉ hỏi “nên dùng bao nhiêu máy?”, bài học này hỏi ngược: nếu muốn giữ một số máy đã chọn, tỉ số chi phí được phép nằm trong khoảng nào?
Ta nghiên cứu mô hình toán học
C(n)=an+\frac bn,\qquad a>0,\quad b>0,\quad
n\in\mathbb N,\quad n\ge1.
Trong đó an tăng theo số máy, còn b/n giảm theo số máy. Hai hạng đều có cùng đơn vị tiền. Trước tiên đây là một mô hình độc lập; khi áp dụng vào sản xuất, ta sẽ nêu rõ cách tính thời gian để biết mô hình có phù hợp không.
Nếu a=10,\ b=62, chọn 2 máy hay 3 máy rẻ hơn? Điểm cân bằng liên tục là \sqrt{6{,}2}\approx2{,}49. Liệu cứ làm tròn đến số nguyên gần nhất có đúng?
Một phản ví dụ cho làm tròn mặc định
C(2)=20+31=51,\qquad
C(3)=30+\frac{62}{3}=\frac{152}{3}<51.
Làm tròn 2{,}49 thành 2 chọn sai. Dù 2 gần mốc liên tục hơn, chi phí tại 3 nhỏ hơn. Ta cần một tiêu chuẩn đúng trên các số nguyên.
2. Chi phí thêm một máy nói lên điều gì?
Đặt \rho=b/a>0. Với mọi số nguyên k\ge1,
C(k+1)-C(k)
=a+\frac{b}{k+1}-\frac bk
=a-\frac{b}{k(k+1)}
=a\left(1-\frac{\rho}{k(k+1)}\right).
Vì a>0 và k(k+1)>0, dấu của hiệu được quyết định bởi việc \rho lớn hơn, bằng hay nhỏ hơn k(k+1):
- Nếu \rho>k(k+1), thêm máy làm chi phí giảm.
- Nếu \rho=k(k+1), hai lựa chọn k và k+1 có cùng chi phí.
- Nếu \rho<k(k+1), thêm máy làm chi phí tăng.
Các ngưỡng k(k+1) tăng nghiêm ngặt, vì
(k+1)(k+2)-k(k+1)=2(k+1)>0.
Do đó dấu của các hiệu chỉ có thể chuyển từ âm sang dương, có thể đi qua một hiệu bằng không. Cấu trúc này cho phép chứng minh cực tiểu trên toàn bộ các số nguyên dương, không chỉ so hai ứng viên gần một mốc đoán trước.
3. Khoảng giá giữ một lựa chọn tối ưu
Cho trước số nguyên n\ge1. Ta chứng minh tiêu chuẩn:
\boxed{n\text{ là một lựa chọn có chi phí nhỏ nhất}
\quad\Longleftrightarrow\quad
n(n-1)\le\frac ba\le n(n+1).}
Vì sao điều kiện là cần?
Nếu n tối ưu, nó không đắt hơn n+1. Vì vậy C(n+1)-C(n)\ge0, suy ra \rho\le n(n+1). Nếu n\ge2, nó cũng không đắt hơn n-1, nên C(n)-C(n-1)\le0, suy ra \rho\ge n(n-1).
Với n=1, không có lựa chọn 0 máy để so sánh. Điều kiện dưới là 0\le\rho, tự đúng do \rho>0. Ta không hề thay n=0 vào công thức có mẫu n.
Vì sao điều kiện là đủ cho cực tiểu toàn cục?
Giả sử hai bất đẳng thức trên đúng. Với mọi 1\le k<n,
k(k+1)\le n(n-1)\le\rho,
nên C(k+1)\le C(k): chi phí không tăng khi đi từ 1 đến n. Với mọi k\ge n,
k(k+1)\ge n(n+1)\ge\rho,
nên C(k+1)\ge C(k): chi phí không giảm từ n trở đi. Vì thế C(n) không lớn hơn bất kì chi phí nào khác.
Mỗi khoảng của n kết thúc đúng nơi khoảng của n+1 bắt đầu. Các ngưỡng tăng không bị chặn, nên với mọi \rho>0 luôn có một lựa chọn tối ưu.
Ba hàng dùng cùng thang đo của tỉ số. Các đầu chung là nơi xảy ra đồng hạng, chẳng hạn tỉ số bằng 6 làm hai lựa chọn 2 và 3 cùng tối ưu.
4. Khi nào có hai lựa chọn cùng rẻ nhất?
Nếu n(n-1)<\rho<n(n+1), các bước trước n giảm nghiêm ngặt và các bước sau n tăng nghiêm ngặt. Do đó n là lựa chọn tối ưu duy nhất. Với n=1, điều này có nghĩa 0<\rho<2.
Tại ngưỡng \rho=n(n+1), ta có C(n)=C(n+1). Mọi bước trước đó đều giảm và mọi bước sau đó đều tăng, nên đúng hai lựa chọn n,n+1 cùng tối ưu. Không thể có ba số máy cùng tối ưu trong mô hình này, vì hai ngưỡng liên tiếp khác nhau.
Ví dụ độc lập: a=10,\ b=60 cho \rho=6=2\cdot3. Hai lựa chọn 2,3 cùng có chi phí 50. Với b=62, tỉ số tăng thành 6{,}2, nằm trong 6<\rho<12, nên chỉ 3 tối ưu. Với b=58, ta có 2<\rho=5{,}8<6, nên chỉ 2 tối ưu.
Nếu mọi giá cùng tăng gấp đôi?
Thay a,b bằng 2a,2b làm mọi C(n) tăng gấp đôi, nhưng tỉ số b/a không đổi. Tập số máy tối ưu được giữ nguyên. Điều quyết định lựa chọn là tỉ số hai hệ số, còn mức tiền tối thiểu phụ thuộc cả độ lớn của chúng.
5. Ứng dụng chọn lọc: khoảng tiền công giữ 15 máy tối ưu
Dữ kiện chọn từ tài liệu nguồn: đơn hàng 10\,000 quả bóng; năng suất mỗi máy 40 quả mỗi giờ; chi phí thiết lập mỗi máy 200 nghìn đồng; một người giám sát toàn bộ các máy được trả 180 nghìn đồng mỗi giờ. Các máy chạy song song.
Ta trước hết dùng mô hình năng suất liên tục : thời gian được tính bằng tổng khối lượng chia tổng năng suất, chi phí giám sát tính đúng thời gian ấy, không làm tròn giờ và chưa áp đặt mỗi sản phẩm phải được làm trọn trên một máy. Khi dùng n máy,
T(n)=\frac{10\,000}{40n}=\frac{250}{n}\text{ giờ}.
Để hỏi về sự thay đổi giá, giữ nguyên các dữ kiện khác và thay tiền công theo giờ bằng w>0, tính bằng nghìn đồng mỗi giờ. Khi đó
C_w(n)=200n+\frac{250w}{n},\qquad
\rho=\frac{250w}{200}=\frac54w.
Theo tiêu chuẩn vừa chứng minh, 15 là một lựa chọn tối ưu khi và chỉ khi
15\cdot14\le\frac54w\le15\cdot16
\quad\Longleftrightarrow\quad
\boxed{168\le w\le192.}
Trong khoảng 168<w<192, chỉ 15 tối ưu. Tại w=168, hai lựa chọn 14,15 cùng có chi phí 5800 nghìn đồng. Tại w=192, hai lựa chọn 15,16 cùng có chi phí 6200 nghìn đồng.
Mức w=180 của dữ kiện nằm trong khoảng, nên 15 là lựa chọn duy nhất của mô hình này:
C_{180}(15)=3000+\frac{45\,000}{15}
=6000\text{ nghìn đồng}.
Thời gian theo mô hình là 250/15=50/3 giờ. Khoảng 168 đến 192 là khoảng tiền công giữ quyết định, không phải khoảng tổng chi phí.
6. Dùng khoảng ổn định để dự đoán thay đổi
Nếu tiền công tăng lên 194 nghìn đồng mỗi giờ, cần tìm lại từ đầu hay chỉ kiểm tra khoảng của số máy kế tiếp? Nếu giảm xuống 166, lựa chọn nào xuất hiện?
Đối chiếu bằng tỉ số
Với w=194, ta có \rho=242{,}5. Vì
16\cdot15=240<242{,}5<272=16\cdot17,
chỉ 16 tối ưu. Với w=166, \rho=207{,}5 và
14\cdot13=182<207{,}5<210=14\cdot15,
nên chỉ 14 tối ưu. Đây là cách chuyển từ một quyết định sang quyết định kế tiếp qua các ngưỡng rõ ràng.
Nếu thay đổi đồng thời chi phí thiết lập và tiền công, không thể chỉ kiểm tra w trong đoạn cũ. Phải tính lại \rho=250w/a. Ví dụ cùng tăng cả a=200 và w=180 lên gấp đôi giữ \rho=225, nên vẫn chọn 15, dù chi phí tiền tăng gấp đôi.
Tiêu chuẩn giả sử mọi số nguyên dương đều được phép. Nếu chỉ có 12 máy, lựa chọn 15 không khả thi. Khi ấy ở mức w=180, mọi bước đến 12 vẫn giảm vì k(k+1)\le12\cdot13<225 với các bước đang xét, nên chọn 12 trong miền được phép. Miền lựa chọn phải đi cùng mục tiêu tối ưu.
7. Nếu từng quả bóng phải được làm trọn trên một máy?
Đây là một mô hình điều chỉnh, có giả thiết rõ hơn: mỗi quả được làm hoàn chỉnh trên một máy trong 1/40 giờ, không chuyển dở sang máy khác; các máy bắt đầu cùng lúc, được chia việc cân bằng nhất; người giám sát được trả đến khi quả cuối cùng xong. Chỉ dùng những máy thực sự nhận việc, nên 1\le n\le10\,000.
Gọi q_n là số nguyên nhỏ nhất sao cho nq_n\ge10\,000. Ít nhất một máy phải làm q_n quả. Ngược lại, dùng phép chia có dư để chia việc cho các máy chênh nhau nhiều nhất một quả sẽ đạt đúng mức này. Vì vậy thời gian tốt nhất là q_n/40, và chi phí là
\widehat C_w(n)=200n+\frac{wq_n}{40}.
Với 15 máy, 10\,000=15\cdot666+10: cho 10 máy làm 667 quả và 5 máy làm 666 quả. Do đó q_{15}=667. Tại w=180,
\widehat C_{180}(15)=3000+\frac{180\cdot667}{40}
=6001{,}5\text{ nghìn đồng}.
Chi phí thay đổi vì cách tính thời gian thay đổi. Công thức an+b/n không còn đúng nguyên dạng; ta phải kiểm tra lại cả khoảng tiền công giữ 15 máy tối ưu.
8. Khoảng ổn định cũng phụ thuộc giả thiết của mô hình
Ta có q_{14}=715,\ q_{15}=667,\ q_{16}=625. So sánh 15 với hai hàng xóm cho các điều kiện cần:
\widehat C_w(15)\le\widehat C_w(14)
\quad\Longleftrightarrow\quad
200\le\frac{48w}{40}
\quad\Longleftrightarrow\quad w\ge\frac{500}{3},
\widehat C_w(15)\le\widehat C_w(16)
\quad\Longleftrightarrow\quad
\frac{42w}{40}\le200
\quad\Longleftrightarrow\quad w\le\frac{4000}{21}.
Chỉ so hai hàng xóm chưa chứng minh cực tiểu toàn cục cho mô hình mới. Các chặn dưới đây hoàn tất bước còn thiếu.
Chứng minh mọi số máy khác đều không rẻ hơn
Với 1\le n\le14, đặt L=667+48(15-n)=1387-48n, là số nguyên. Ta có
n(L-1)=n(1386-48n)\le14(1386-48\cdot14)=9996<10\,000.
Bất đẳng thức giữa hai biểu thức đầu được kiểm tra bằng hiệu
9996-n(1386-48n)=(14-n)(714-48n)\ge0.
Vì n(L-1)<10\,000, một máy không thể chỉ cần nhiều nhất L-1 quả trong cách chia cân bằng, tức q_n\ge L. Suy ra
\widehat C_w(n)-\widehat C_w(15)
\ge(15-n)\left(-200+\frac{48w}{40}\right)\ge0
\quad\text{khi }w\ge\frac{500}{3}.
Với n\ge16, ta có
10\,000-n(1297-42n)
=(n-16)(42n-625)\ge0.
Do q_n\ge10\,000/n, suy ra q_n\ge1297-42n, hay 667-q_n\le42(n-15). Vì thế
\widehat C_w(n)-\widehat C_w(15)
\ge(n-15)\left(200-\frac{42w}{40}\right)\ge0
\quad\text{khi }w\le\frac{4000}{21}.
Hai chặn phủ mọi n\ne15 trong miền cho phép. Khi cả hai điều kiện đều nghiêm ngặt, mọi hiệu đều dương, nên chỉ 15 tối ưu. Khi vượt ra ngoài một trong hai biên, so sánh với 14 hoặc 16 đã cho một lựa chọn rẻ hơn.
Vậy điều kiện cần và đủ trong mô hình sản phẩm nguyên là
\boxed{\frac{500}{3}\le w\le\frac{4000}{21}}
\qquad\left(\text{xấp xỉ }166{,}67\le w\le190{,}48\right).
Các số thập phân chỉ để hình dung; khi kiểm tra sát biên, phải dùng các phân số chính xác. Mức 180 vẫn thuộc phần trong của đoạn, nên 15 máy vẫn tối ưu duy nhất, với chi phí 6001{,}5 nghìn đồng đã tính.
Hai hàng dùng cùng thang đo tiền công. Chấm nâu ở mỗi hàng là mức 180; các đầu xanh đều được lấy. Khoảng thay đổi khi giả thiết về cách chia sản phẩm thay đổi.
Hai mô hình có thể chọn khác nhau ngay cả khi các con số ban đầu gần nhau. Tại w=167, mô hình năng suất liên tục chọn 14, vì \rho=208{,}75<210; mô hình sản phẩm nguyên chọn 15, vì 500/3<167<4000/21. Đây là hậu quả có thể kiểm chứng của giả thiết chia việc, không phải lỗi làm tròn của công thức.
9. Một quyết định tốt cần cả khoảng giá và miền áp dụng
Với mô hình an+b/n, hãy dùng tỉ số b/a và các ngưỡng n(n+1) để xác định quyết định, trường hợp hòa và khoảng giá giữ quyết định ấy. Nếu đổi cách tính thời gian, làm tròn sản phẩm hoặc giới hạn số máy, hãy dựng lại miền và công thức trước khi dùng khoảng cũ.
Chứng minh “tối ưu” đòi hỏi so được với mọi lựa chọn hợp lệ. Một công cụ mạnh là tìm dấu của mọi hiệu liên tiếp; một công cụ khác là chặn trực tiếp hiệu với lựa chọn đang xét. Các phép so sánh hai chiều giúp biết cả khi nào quyết định còn đúng và khi nào nó chắc chắn phải đổi.
Tự học có chứng minh · Toán THCS · Các hình dựng đúng quan hệ đã nêu