Тәжірибелік есептерін симплекс әдісімен шығару
Кіріспе
Математикалық программалау — өмірдің нақты қажеттіліктерінен туындаған қолданбалы математиканың аса маңызды салаларының бірі. Оның ішінде халық шаруашылығында кең қолданылып, әдістері терең зерттелген бағыт — сызықты программалау.
Сызықты программалаудың қалыптасуы
Сызықты программалау есептері алғаш рет ХХ ғасырдың 1930-жылдары жарияланып, кейіннен математикалық программалаудың негізгі бөліміне айналды. Мұндай есептердің құрылымы салыстырмалы түрде қарапайым болғандықтан, олар тәжірибелік міндеттерді модельдеуге және зерттеуге қолайлы.
Негізгі ой
Сызықты программалау — қолданбалы есептерді тиімді жоспарлау мен оңтайландыруға арналған әмбебап құрал.
Түйін ұғымдар
- оңтайландыру
- сызықты модель
- алгоритм
Ерте зерттеулер және «венгер әдісі»
Сызықты программалаудың дербес бағыттарының бірі — қатынас есебі. Оның жеке түрі 1931 жылы Венгрияда жарияланды; мақаланың авторы — математик Эгервари. Кейін бұл жұмыс негізінде бірқатар еңбектер жазылды. Мысалы, 1951 және 1956 жылдары Кун Х.В. мен Теккер А.В., ал 1957 жылы Форд Х.Р. және Фалкерсон Д.Р. қатынас есептерін шешу әдістерін дамытты.
Осы зерттеулердің нәтижесінде әдебиеттерде бұл тәсілдер жиынтығы «венгер әдісі» деген атаумен орнықты.
Терминнің орнығуы және Хичкок жұмысы
«Сызықты программалау» термині алғаш рет 1940-жылдары АҚШ-та кеңінен қолданыла бастады. Бұл бағыттағы арнайы есептердің бірі 1941 жылы АҚШ-та жарияланып, оның авторы Хичкок Ф.Л. болды.
Канторович, потенциал әдісі және симплекс
Бұрынғы Кеңестер Одағында сызықты программалаудың негізін қалаушылардың бірі — академик Л.В. Канторович. Оның сызықты программалауға арналған дербес есептері 1930-жылдардан бастап жариялана бастады.
1956 жылы Дж. Данциг, Х.Р. Форд және Д.Р. Фалкерсон венгер әдісі негізінде сызықты программалау есептерін шешуге арналған, Канторович ұсынған потенциал әдісіне мазмұндас тәсілді ұсынды.
1947
Дж. Данциг сызықты программалаудың әмбебап симплекс әдісін ұсынды.
1939
Канторович ұсынған біртіндеп жақсарту әдісі симплекс тәсіліне өте жақын болды.
Өкінішке қарай, Канторович бұл идеяларды ертерек ұсынғанына қарамастан, көптеген әдебиеттер мен оқулықтарда симплекс әдісі Данциг әдісі ретінде аталып жүр.
Алдағы бөлімдерге қысқаша бағдар
- I-тарауда симплекс әдісінің алгоритмі кезең-кезеңімен қарастырылады.
- II-тарауда тәжірибелік есептер симплекс әдісі арқылы шығарылып, нәтижелер талданады.