159
сұлбасы кеңінен қолданылады. Толық бұтақталғаннан кейін кезекті қадамда Ωi , i= 1, 3, 21,
22, 23 барлық соңғы жиындар бағаларынан у минималды мәні бар Ω1 жиыны ары қарай
бұтақталу үшін алынады.
Кезекті қадамда біржақты бұтақталған кезде Ω21, Ω22, Ω23 алдыңғы қадамда
бұтақталған кезде алынған жиындардың арасында минималды бағасы бар Ω21 жиыны
бұтақталуға жатады.
Бұтақталған кезде пайда болатын жиындар қосылу бойынша реттелген және олардың
арасындағы байланысты толық бұтақталу кезінде бірэлементті жиындарға жауап беретін
ілінген шыңдарымен (соңғы жиындармен) Ω жиынына жауап беретін тамырымен (H ,U)
шешімі ішкі жиындар ағашы түрінде бейнелеуге болады.
Ω ішкі жиынының Н жиынында анықталған у сандық функцисын бұтақталу бағасы
жүйесі деп атаймыз. Бұтақталу кезінде жиында бұл функцияның мәнін осы жиынның бағасы
деп атамыз. Осыдан кейін "бұтақталу" және "жиын бағасы" түсініктері енгізілгеннен кейін Б
және Ш әдісінің қалыптасқан анықтамасын беруге болады.
Дискретті бағдарламалаудың есебін шешу үшін бұтақтар және шекаралар әдісі деп Оi
жиындардың бұтақталу алгоритмін және минимизация есептерінде келесі шарттарды
қанағаттандыратын сонымен байланысты у жиындардың бағалар жүйесін айтуға болады.
Бұтақтар мен шекаралар әдісінің негізінде мүмкін шешімдер жиынын кіші жиындарға
тізбекті бӛлу жатыр. Әдістің әр қадамында бұл кіші жиын нақты шешімі бар ма жоқ па соны
анықтау үшін бӛлу элементтері тексеріледі. Тексеру негізі тӛменгі бағаны шешу арқылы
белгілі болады. Егер қандай да бір жиыншаның тӛменгі бағасы рекорд болып белгіленген
бағадан кіші болса, онда ары қарай сол жиынша қарастырылады. Егер қарастырылған
жиыншаның табылған тӛменгі бағасы рекорд болып белгіленген бағадан кіші болса, онда
рекорд ауыстырылады. Алгоритмнің соңында рекорд сол жұмыстың шешімі болып
табылады. Егер бӛлінетін элементтердің барлығын алып тастау мүмкін болса,яғни рекорд
болып белгіленген бағадан үлкен болса онда рекорд – дұрыс шешім болып табылады. Ал
егер олай болмаса алынбаған кіші жиындардан перспективті жиынша табылып,
тармақталады. Жаңа кіші жиыншалар тексеріске ұшырайды және т.с.с.
Тағайындау есебінің моделін келтірейік. Жұмыс жиыны А ={A1,…,Ai,…,Am};
орындаушылар жиыны В={В1,…,Вj,…,Вn}; уақытты шығындау матрицасы T = || t
ij
||,
мұндағы t
ij
— j-ші жұмысшының і-ші жұмысты орындауғa кеткен уақыты, бұл жерде i =
1,m; j = 1,n болсын. Сондай-ақ әрбір орындаушы бірнеше жұмысты орындауы мүмкін, ал
әрбір жұмыс тек қана бір жұмысшыға беріледі. Онда жұмыстарды жұмысшыларға, жұмыстар
мүмкін минималды уақытта орындалатындай етіп, тарату керек . Жобамен S = {l,...,s,...,s
0
}—
жұмыстарды жұмысшыларға жіктеу нұсқаларының жиынын алайық, мұндағы s
0
—
жұмыстарды жұмысшыларға жіктеу нұсқаларының жалпы саны . Nj(s) s-ші нұсқадағы j-ші
жұмысшыға тағайындалған жұмыстар жиыны. Онда j–ші жұмысшының s-ші нұсқадағы
шығындалу уақыты:
S–ші нұсқадағы барлық жұмыстардың орындалуының аяқталу уақыты
жұмысшылардың жұмысты орындауға жұмсаған максималды уақытымен анықталады:
T{s} = max T
j
(s).
Онда S ңұсқаларының ішінен T(ℓ)=min T(s) болатын, ℓ € S нұсқасын таңдап алу
керек.
Есепті шешу алгоритмі:
Глобальді параметрлерді анықтаймыз.
1. Шеткі нүктені табатын function max анықтаймыз
2. LabeledEdit1 арқылы жұмыс санын (m) береміз. Оған байланысты StringGrid1 және 2-
)
(
)
(
s
N
i
ij
j
j
t
s
T
160
нің биіктіктері ӛзгереді
3. LabeledEdit2 арқылы жұмысшы санын (n) береміз. Оған байланысты StringGrid1,
4(d1,d2,d3,e), 5(*2 есе), 6(2* есе)-ның ені ӛзгереді
4. Button1Click арқылы StringGrid1-ге элементтер енгіземіз
5. Button2Click арқылы StringGrid2-ні толтырамыз, яғни 1-жол —Т(тау) табады, 2-жол—
Z табады, 3-жол—сумма Т табады. Button3.Visible:=true
6. Button3Click арқылы Этап 0-ді есептейміз, яғни d1,d2,e-ні. Нәтижелерді StringGrid4-
ке жазамыз. Button3.Visible:=false; Button4.Visible:=true;
7. Button4Click арқылы а) Z-ті Zkontrol арқылы анықтаймыз (алғашында ол 1-ге тең); в)
m және Z айнымалыларын салыстырамыз. Егер m үлкен болса, онда Button10.Click
орындалады және Zkontrol 1-ге ӛседі; с) Егер m кіші болса, онда цикл аяқталып ―бітті‖ сӛзі
шығады
8. Button10Click арқылы Этап Z-ті есептеп отырамыз.
a) Локальді айнымалыларды анықтаймыз
b) StringGrid6-ны тазалаймыз (компьютер жадысы босау үшін)
c) for t:=1 to StringGrid3.RowCount do циклін жібереміз. Егер StringGrid3-тің қатары бос
болса, онда тоқтаймыз(R1 Label-ге ӛтеміз). Бос болмаса StringGrid5-тің ячейкаларына 0,1,2,...
(жұмыс нӛмерлерін ) қоямыз.
d) Кейін StringGrid5-тің толтырылған ячейкалары(жұмыс нӛмерлерін ) бойынша
StringGrid1-ден осы жұмыстарға кететін уақыттарды есептейміз
e) StringGrid4-ке d1,d2,d3,e-ні толтырамыз.
f) StringGrid6-ны толтырамыз: Оған белгілі этапта орындалған барлық мәліметтерді
жазамыз, яғни жұмыстың қай жұмысшыға берілгенін, оны орындауға қанша уақыт
жұмсағанын
g) Цикл аяқталғасын R1 Label-ге ӛтеміз.
h) StringGrid3-ті толтырып шығамыз: шеткі нүкте, жұмысшы, жұмыс, таралу тарихы,
соңғы оқиға
9. Қайтадан Button4-ті басамыз.
Осы алгоритмді пайдаланып тағайындау есебін шығаратын программа құрылды.
Әдебиеттер тізімі:
1. Черноморов Г.А. Теория принятия решений. —Новочеркасск: 2002, 276 б. [36-46].
2. Кузнецов Н.А., Кульба В.В., Косяченко С.А., Казиев Г.З. Модели и методы
проектирования модульных информационно-управляющих систем. // Автоматика и
телемеханика. М.:- 1994.
3. Г.З.Казиев. Блочно-симметричные модели и методы постановки и решения задач
дискретного программирования. // Вестник Инженерной Академии Республики Казахстан.
2003г.-№2(10), 55-59 б.
4. Корбут В., Вилькейнштейн А. Дискретное программирование. М.-1969г.
Аннотация
Ұсынылып отырған мақаланың мақсаты келесі тапсырмаларды автоматты түрде орындауға
мүмкіндік беретін бағдарлама құрастыру. Бұтақтар мен шекаралар әдісін тағайындау есебін шешеуде
қолдану арқылы автоматтандырылған бағдарлама ұсынылған. Бұтақтар мен шекаралар әдісінің
мақсаты нақты шешім табу болып табылады. Мақалада сызықтық программалау тапсырмалары
қарастырылған.
Аннотация
Целью статьи является создание программы, которая автоматизировала бы выполнение
следующих задач. Метод ветвей и границ относится к комбинаторным методам решения
целочисленных задач и применим как к полностью, так и к частично целочисленным задачам. Суть
метода ветвей и границ – в направленном частичном переборе допустимых решений. Будем
рассматривать задачу линейного программирования.
Достарыңызбен бөлісу: |
