Бутун сонли дастурлаш масаласи

1.

ЛЕКЦИЯ 4. БУТУН СОНЛИ ДАСТУРЛАШ
МАСАЛАСИ
РЕЖА:
1. БУТУН СОНЛИ ДАСТУРЛАШ
МАСАЛАСИ
2. МАСАЛАНИНГ ҚЎЙИЛИШИ
3. ТАЙИНЛАШ МАСАЛАСИ
ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ЗАДАЧИ О НАЗНАЧЕНИЯХ © А.А. ОМОНОВ, 2018-2019
1/18

2.

БУТУН СОНЛИ ДАСТУРЛАШ
МАСАЛАСИ
2/
• БУТУН СОНЛИ ДАСТУРЛАШ
МАСАЛАСИ (БСД) ЧИЗИҚЛИ
ДАСТУРЛАШНИНГ ШУНДАЙ
МАСАЛАЛАРИНИ ЕЧИШГА
МЎЛЖАЛЛАНГАНКИ, УЛАРДА БАРЧА
ЁКИ АЙРИМ ЎЗГАРУВЧИЛАР БУТУН
(ЁКИ ДИСКРЕТ) ҚИЙМАТЛАР ҚАБУЛ
ҚИЛИШИ КЕРАК.
ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ЗАДАЧИ О
НАЗНАЧЕНИЯХ © А.А. Омонов, 2018-2019
13

3.

Butun sonli dasturlash masalasi
ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ЗАДАЧИ О
НАЗНАЧЕНИЯХ © А.А. Омонов, 2018-2019
3/
18

4.

Butun sonli dasturlash masalasi
ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ЗАДАЧИ О
НАЗНАЧЕНИЯХ © А.А. Омонов, 2018-2019
4/
18

5.

БУТУН СОНЛИ ДАСТУРЛАШ
• Бундай масалаларни ечиш чекли
сондаги махсус чизиқли дастурлаш
масалаларини кетма кетлигини ечишга
келтирилади:
Бунда ҳар масала олдингисига кесма
деб аталувчи қўшимча чизиқли шарт
(тенгсизлик) қўшиш билан ҳосил
қилинади
5/
13

6.

БУТУН СОНЛИ ДАСТУРЛАШ
6/
Бунда l – кесма деб Pl-1 масалани ҳосил
қилиш учун масалага қўшилувчи ва
қуйидаги 2 та шартни қаноатлантирувчи
чизиқли чекловга айтилади:
• Pl-1 масалани қаноатлантирувчи ихтиёрий
бутун ечим берилган масалани
қаноатлантиради;
• Pl-1 масаланинг ихтиёрий бутун бўлмаган
ечими берилган масалани ҳам берилган
масалани қаноатлантирмайди. («кесиб
ташланади»).
13

7.

БУТУН СОНЛИ ДАСТУРЛАШ
Pl-1 масала симплекс метод билан ечилган ва унинг
ечими бутун бўлмасин. Белгилашлар:
k — сўнгги симплекс жадвалдаги эркин ўзгарувчилар индекси,
s — шу жадвалдаги энг катта қийматли сатр рақами
• У ҳолда тўла бутун сонли масала ечими
учун I Гомори кесмаси ушбудир:

8.

БУТУН СОНЛИ ДАСТУРЛАШ
• ГомориI I кесмаси, қисман бутун сонли
масала учун қўлланилади (уни тўла бутун
сонли масала учун ҳам қўллаш мумкин)
ва ушбу кўринишда
• бунда ask— коэффициентлар қуйидаги
муносабаатлардан аниқланади:
8/
18

9.

для
не подчиненных требованиям целочисленности,
для
(3)
подчиненных требованиям целочисленности,
(4)

10.

10/
18
Тўла ёки қисман бутун сонли дастурлаш
масаласи ҳар бири қуйидаги пунктлардан иборат
итерациялар кетма-кетлиги кўринишида
бажарилади:
1) Pl-1 масала ечилади ва унинг
оптимал ечими топилади,
2) Агар бу
ечим бутун бўлса, жараён тугайди, акс
ҳолда 3) пунктга ўтилади
3) Сўнгги симплекс жадвал асосида Гомори кесмалари
топилади (I ёки II)
4) Олдинги пунктда топилган кесмани Pl-1 масалага
қўшилади ва бу Pl масалани беради ва яна 1) пунктга
қайтилади.

11.

3.1. ТАЙИНЛАШЛАР МАСАЛАСИ
• n ишчилар
• n иш ўрни
Берилган:
• Iишчининг j ишдаги келтирган
фойдаси
Топинг:
• Фойдани максималлаштирувчи
оптимал тайнловни топиш
11

12.

ЛИТЕРАТУРА
Экономико-математические методы и прикладные
модели: Учеб. пособие для вузов / Под ред. В.В.
Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. — раздел
3.2.
Фомин Г.П. Математические методы и модели в
коммерческой деятельности: Учебник. – 2-е изд. М.:
Финансы и статистика, 2005. — раздел 2.2.6.
Вентцель Е.С. Исследование операций: Задачи,
принципы, методология. М.: Высшая школа, 2001.
ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ЗАДАЧИ О НАЗНАЧЕНИЯХ © А.А. ОМОНОВ, 2018-2019
12