Сызықтық бағдарламалау есептері
М а з м ұ н
Кіріспе ………………………………………………………………………..
3
І-тарау. Сызықтық бағдарламалау есептері ...........................................
1.1. Сызықтық бағдарламалау есептерінің берілуінің негізгі
1.2. Сызықтық бағдарламалау есебнің жалпы берілуі
ІІ-тарау. Жүкті тасымалдау тиімді есебі
2.1. Бастапқы жоспарды анықтаудағы солтүстік -
11
2.2. Бастапқы жоспарды анықтаудағы ең кіші
Қорытынды …………………………………………………………………
Пайдаланылған әдебиеттер
16
Кіріспе
Экономика-математикалық модельдің өңделу және орындалу процесі
● Есептердің берілуі;
● Модельдердің орындалуы;
● Модельдерді шешудің алгоритмі немесе математикалық
● ЭЕМ-де есептерді шешу және шешімдердің
Есептің берілгеніне ерекше мән беру керек
Экономика-математикалық модельдерді орналастыру және орындау есептің
Математикалық модельдерді орындау жүйені жеткілікті түрде
Математикалық модельді құрастырудың негізгі мақсаты жай
Берілген кезеңді жүзеге асыру үшін жеткілікті
Модельдерді тұжырымдауды өте жақсы жүзеге асырушы
Модельді шешудің алгоритмін немесе математикалық әдісін
Модельдің шешімінің нәтижесінің экономикалық интерпретациясы экономикалық
Тиімді жоспарды табу нақты, ыңғайлы жоспармен
Осындай анализдеу процесінде біріншіден, қарастырылушы варианттар
I-тарау. Сызықтық бағдарламалау есептері
1.1. Сызықтық бағдарламалау есептерінің берілуінің негізгі
Экономикадағы тиімді есептер мекемедегі жоспарлардың салалық
Мекемеге байланысты өндірістің тиімді есептері максимальды
Сызықтық бағдарламалаудың дербес жағдайларына берілетін есептерді
Фабрика айлық өндірістік бағдарламасында ресурстың үш
Кесте 1.1.1
Ресурстар
Шығатын ресурстар нормасы бірлік өніммен Нақты
Продукция 1 Продукция 2 Продукция 3
Еңбек, адам/күн
7 2 2 6 800
Шикізат, т 5 8 4 3
Құрал-сайман, станок/сағ 2 4 1 8
Бағасы мың сом 3 4 10
Өнімнің өндірістік жоспарын табу және оны
мұндағы X= (x1, x2, x3, x4)T
1.2. Сызықтық бағдарламалау есебнің жалпы берілуі
Сызықтық бағдарламалаудың есебі жалпы түрде берілгенде
СПЕ-нің еркін формадағы түрі
Берілген өрнек мақсатты функциялық (немесе критерийлік)
(Х1, Х2 ,…, Хn) – есептегі
Әрбір теңсіздік жарты кеңістікті анықтайды, ал
Х* = (Х*1, Х*2, …, Х*n)
Егер D облысы шектелген болса, онда
Егер мақсатты функцияның градиенті c =
Егер шектеулер тәуелсіз болса немесе мақсатты
Егер D облысы шектелмеген болса, онда
Кез-келген минимумға берілген есеп максимумға берілген
СПЕ-нің максимумға берілген симметриялық формасы
Есептің минимумға берілген симметриялық формасы төмендегідей:
Егер барлық bi ≥ 0 болса,
Өнімнің Х* = (Х*1,
Тиімді жоспардағы қол жеткен теңдік шектеуі
СПЕ конондық формасы төменде көрсетілген:
Сызықтық алгебрадан белгілі, сызықтық белгісіз теңдеулер
Анықтама: Егер (1.2.4) есебінің коэффициенті 1-ге
Егер базистік айнымалы барлық шектеуде бар
(1.2.4) шартшын қанағаттандыратын кез келген векторды
Егер конондық формадағы барлық bi ≥
Айнымалы базистік деп аталады, егер теңсіздіктің
Келесі түрлендірулердің нәтижесінде кез келген СПЕ
● айнымалы енгізу, егер кез келген
● баланстық айнымалы енгізу.
Егер СПЕ конондық формадағы шектеуде базистік
Жасанды айнымалы енгізу және мақсатты функцияның
Мысалы СП есебі төмендегідей түрде болсын:
Конондық формаға келтіру үшін x2=x12−x22 алмастыруын
Кез келген экономикалық жүйе, салыстырмалы түрде
Жалпы жағдайда, басқа бір объектілердің (оның
Әдебиетте экономика-математикалық модельдеудің қалыптасқан анықтамасы жоқ,
Басқа сөзбен айтқанда, экономика-математикалық модель –
Көрсетілген тәуелділіктер қарым-қатынасы әйтеуір бір деңгейде
Бұлардың өзгеру траекториялары модельдің (өтілуінің) шығарылуының
Экономика-математикалық модельдеудің талай рет өткізілуі осы
Модельді қолданып басқару процесін бұл жағдайда
Сурет 1. Модельдеу принципін қолдану сызбасы.
Сурет1-де көрсетілгендей шешуге апаратын «тікелей» жол
Сонымен, экономика-математикалық модельдеу тәсілін қолдану, бізге
Модельде сандар зерттеулері арқылы әртүрлі жағдайда
Әрі қарай модель тәртібі арқылы ол
Экономика-математикалық модельдеу принципін қолданғанда, материалдық және
Экономика-математикалық модельдеудің ерекше ролі – жоғары
Қазіргі уақытқа дейін осы жағдай тек
Сонымен есепті шығарып жатқан ЭЕМ қолданушыға,
Сонымен, басқарушыға, есептеуіш техниканы тек қана
«Мұның болып жатқаны, машинаға не керектігін
Экономика-математикалық модельдеу, экономикалық жүйелерді зерттеудің қазіргі
( методологиялық жоспарда – экономикалық теориямен;
( методикалық қатынаста – халық шаруашылығы
( математикалық аспекте – математикалық бағдарламалау,
ІІ-тарау. Жүкті тасымалдауды тиімді жоспарлаудың математикалық
2.1. Бастапқы жоспарды анықтаудағы солтүстік -
Айталық жүкті жөнелтетін A1, A2,…,Am станциялардың
Бізден жүктерді Ai станциялардан Bj. станцияларға
Кесте A
Тасымалдау станциялары A1 A2 A3
Қабылдау станциялары
B1 c11 c21 c31
B2 c12 c22 c32
B3 c13 c23 c33
Bn-1 c1n-1 c2n-1 c3n-1
Bn c1n c2n c3n
Қорлар a1 a2 a3
Егер
Егер xij – Ai
(2.1)
,
F = c11x11 + c12x12 +…+
Нәтижеде алынған математикалық модель, жүкті тиімді
Жүкті тиімді тасымалдау есебін шешуде потенциалдар
Солтүстік –батыс бұрыш әдісінің алгоритмін толық
Кесте A
Тасымалдау станциялары A1 A2 A3
Қабылдау станциялары
B1 c11 c21 c31
B2 c12 c22 c32
B3 c13 c23 c33
Bn-1 c1n-1 c2n-1 c3n-1
Bn c1n c2n c3n
Қорлар a1 a2 a3
Солтүстік –батыс бұрышындағы ұяшықты таңдап аламыз.
Мән x11 былайша анықталады: x11=min(a1,b1).
Кесте B
Тасымалдау станциялары A1 A2 A3
Қабылдау станциялары
B1 c11 c21 c31
B2 c12 c22 c32
B3 c13 c23 c33
Bn-1 c1n-1 c2n-1 c3n-1
Bn c1n c2n c3n
Қорлар a1- b1 a2 a3
Нәтижеде алынған В кестедегі солтүстік –батыс
Айталық, x12= a1 - b1, бұл
Жоғарыда сипатталған алгоритмді келесі мысалда көрсетеміз.
Кесте C
Тасымалдау станциялары A1 A2 A3 Қабылдай
Қабылдау станциялары
B1 x11 x21 x31 180
B2 x12 X22 x32 30
B3 x13 X23 x33 250
B4 x1n X2n x3n 120
Қорлар 140 300 140 580
Мұнда 140, 300, 140 жүктер
Солтүстік-батыс бұрыш ұяшығындағы x11 –
x11 = min(a1, b1)= min(140, 180)=140.
A1 станцияда жүк қалмағаны үшін,
Нәтижеде келесі кестені аламыз:
Кесте D
Тасымалдау станциялары A1 A2 A3 Қабылдай
Қабылдау станциялары
B1 140 x21 x31 40
B2 0 x22 x32 30
B3 0 x23 x33 250
B4 0 x2n x34 120
Қорлар * 300 140 580
Келесі солтүстік-батыс бұрыш ұяшығы x21
Кесте E
Тасымалдау станциялары A1 A2 A3 Қабылдай
Қабылдау станциялары
B1 140 40 0 *
B2 0 x22 x32 30
B3 0 x23 x33 250
B4 0 x2n x34 120
Қорлар * 260 140 580
Мұнда мына ұяшықты толтыру қажет: x22
Нәтижеде Кесте F аламыз. F кесте
Кесте F
Тасымалдау станциялары A1 A2 A3 Қабылдай
Қабылдау станциялары
B1 140 40 0 120
B2 0 30 0 30
B3 0 230 20 250
B4 0 0 120 120
Қорлар * 260 140 580
2.2. Бастапқы жоспарды анықтаудағы ең кіші
Бұл әдісте ұяшықты толтыру солтүстік бұрыштан
Кесте G
Тасымалдау станциялары A1 A2 A3 Қабылдай
Қабылдау станциялары
B1 x11 3 x21 2 x31
B2 x12 5 x22 6 x32
B3 x13 6 x23 5 x33
B4 x14 8 x24 3 x34
Қорлар 140 300 140 580
Ең кіші қаражат A2 станциядан
Кесте G
Тасымалдау станциялары A1 A2 A3 Қабылдай
Қабылдау станциялары
B1 0 3 180 2 0
B2 x12 5 x22 6 x32
B3 x13 6 x23 5 x33
B4 x14 8 x24 3 x34
Қорлар 140 120 140 580
Келесі ең кіші қаражаты болған ұяшық
x24 = min(a2, b4)=min(120,120). Бұл амалдарды
Кесте I
Тасымалдау станциялары A1 A2 A3 Қабылдай
Қабылдау станциялары
B1 0 3 180 2
B2 30 5 0 6
B3 110 6 0
B4 0 8 120 3
Қорлар 140 300 140 580
Солтүстік батыс бұрыш әдісі бойынша есептелінген
F= 2*180 +5*30 + 6*110 +
Қорытынды
Кез келген есеп үшін математикалық
Курстық жұмыста жүкті тиімді тасымалдау есебінің
Қорыта айтқанда бұл моделді басқа саладағы
Пайдаланылған әдебиеттер
Банди Б. Основы линейного программирования. -М.:
Каримов А.К. Математикалық моделдеудің өмірдегі орны.-Алматы:Қазақ
Булавский В.А., Звягина Р.А., Яковлева М.А.
Вершинин О.Е. Компьютер для менеджера. -М.:
Еремин И.И., Астафьев Н.Н. Введение в
Карасев А.Н., Кремер Н.Ш., Савельева Т.Н.
Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б.
Лищенко В.Л. Линейное и нелинейное
Распин Л.Г., Кириченко И.О. Многоиндексные задачи
Юдин Д.Б., Гольдштейн Е.Г. Линейное программирование.
Файсман А. Профессиональное программирование на Турбо-Паскале.
Мартин Дж. Организация баз данных в
Цикритзис Д., Лоховски Ф. Модели данных.
16
(1.2.5)
(1.2.4.)
(1.2.3)
(1.2.2)
(1.2.1)
Есептің Модельдің
Берілуі жасалуы
(1.1.1)
(1.2.6)
Сызықты программалау есептері және оларды шешу әдістері
Экономикалық процестерді зерттеудегі сызықтық бағдарламалау модельдері
Қолданбалы математика
Сызықтық бағдарламалаудың қосалқы есептері және оның экономикалық интерпретациясы
Беллманның оңтайлау принципі. Динамикалық программалау есебін шешудің әдісі
Сызықтық бағдарламалау есептерінің графиктік түсіндірмесі
Сызықты және математикалық программалау
«Модель типтері мен олардың түпнұсқасымен ұқсастық түрлері»
Паскаль тілінде сызықтық бағдарлама құру
Мақсат функциясы және математикалық программалау есебінің шектемелері