Базистік шешімдерді табу
Жоспар
Кіріспе 3
Негізгі бөлім. 4
1 Тиімділік есептерінің модельдері 4
2.Сызықты теңдеулерге арналған есептердің мысалдары 6
3. Екі айнымалысы бар сызықтық теңдеулердің графикалық
4. Тасымалдау есебін шешу. 11
5. Тиімділік есебнің программасын құру және компьютер көмегімен
Қорытынды 31
Кіріспе
Қазіргі кезде тасымалдау, машина жасау, ауыл шаруашылғы
Тиімді әдістерді табу есептері сан алуан, мұндай
Қазіргі кезде әр түрлі тасымалдау есептерін шығарудың көптеген
Сызықты программалаудың математикалық аппаратының негізін салған академик Кантарович
Әр түрлі процесстерді сипаттау үшін математикалық модельдер жасалады,
Тиімділік моделінің жалпы құрылысын қарастырайық.
Негізгі бөлім.
1 Тиімділік есептерінің модельдері
Алдымен бір процесті немесе бір құбылысты басқаруда қандай
Берілген процесті не құбылысты М математикалық модель арқылы
Әрбір әрекетті сандық нәтижесін бағалауға болатын болса, әрбір
Белгілі бір мақсатқа бағытталған әрекет - жақсы нәтижеге
u
барлық u-ларды қарастырайық.
Мұндай есеп экстремалды немесе тиімділік есеп деп
Барлық ғылымдар сияқты, экономика ғылымы да мынадай сұрақтарға
Экономикалық мәселелердің шешу жолдары қандай болатыңдығын түсіну үшін
Ең алдымен негізгі факторларды атап өтейік: жер көлемі,
Экономиканың кез келген саласында осындай мәселелер туындап отырады.
Айталық, біз қарастырып отырған есепте осындай факторларды бөліп
Бұл сұрақтарға жауап беру үшін маңызды факторларды сандық,
2.Сызықты теңдеулерге арналған есептердің мысалдары
Есеп 1. Цех екі түрлі трансформатор өндіреді. Бірінші
трансформатордың біреуіне 5 кг трансформаторлық темір мен 3
екінші түрінің бір трансформаторына 3 кг темір мен
Бірінші түрдегі трансформатордың біреуінен цехтың көретін пайдасы
х1 және х2 сәйкесінше бірінші және екінші түрдегі
5х1+ 3х2 480
3х1+2 х2 300
Теңсіздік белгісі цехтың темір мен
Осы екі айнымалылы сызықты функцияның ең үлкен (максимал)
Соңғы х1 х2
Есеп 2. Фермадағы малды қоректендіру үшін оларға күнделікті
А В С 1 массалық бірліктің бағасы
1 жем түрі массалық 4
бірлікте
бірл бірл 1 бірл 20 теңге
2 жем түрі массалық 3
бірлікте
бірл бірл
3 жем түрі массалық 2
бірлікте
бірл бірл
А, В, С
х1, х2 және х3 арқылы 1, 2, 3
А, В, С, қоректік
қанағаттандырады:
4х1 +3х2 + 2х3 33
3х1+ 2х2 + х3 23
х1+х2 +2х3 12
Ал күнделікті қоректің бағасы z=20х1+20х2+10х3 функциясымен анықталады.
Есептің мағынасы бойынша
мәндері келесі теңсіздіктер жүйесін қанағаттандыруы керек:
4х1 +3х2 + 2х3 33
3х1+ 2х2 + х3 23
х1+х2 +2х3 12
х1 0, х2 х3
Жоғарыда қарастырылған есептер өздерінің мазмұны бойынша оптималдық есеп
Ең кіші немесе ең үлкен мәні есептелетін функция
5х1+3х2 480
3х1+2х2 300
х1 0, х2 0
Анықтама 1. Шектеу жүйесінің кез келген шешімі сызықты
Мысалы: 1- есептегі шектеу жүйесінің шешімі х1
Анықтама 2. Мақсат функциясы максимал (минимал) мәніне жететіндей
Сызықты программалаудың барлық есептерін екі түрге жіктеуге болады.
Алайда mаx z =
Жалпы жағдайда оптимизациялау есебі келесі түрде анықталады. Айнымалылар
шарттарын қанағаттандыратындай х1 х2 ,.., хn
3. Екі айнымалысы бар сызықтық теңдеулердің графикалық
Екі айнымалысы бар сызықты
a11х1+ a12х2 b1
a21х1+ a22х2 b2
…………………
an1х1+ an2х2 bn
шарттарын қанағаттандыратындай хь х2 белгісіздері арасында
Шектеу жүйесі сызықты теңсіздіктерден тұратын болғандықтан, оның шешімдер
Осыған байланысты есептің қойылуын өзгеше айтуға болады: М
Сызықты функциясының ең үлкен (ең кіші) мәніне жеткізетін
Егер z= d мәнін тұрақты етіп алсақ, онда
с1х1 + с2х2 = d. Бұл теңдеудің шешімдері
(1-сурет).
1- Сурет.
М дөңес көпбұрышы шектеу жүйесінің шешімі болсын. Онда
2-сурет.
Кейбір жағдайда с1х1 +с2х2 =d, түзуі көпбұрыштың бір
мүмкін (3-сурет)
3-сурет
Бұл М көпбұрышында с1х1 +с2х2=d түзуіне параллель
Осылайша 3-суретте мақсат функциясының максимал мәні АВ қабырғасымен,
Жүйенің мәндер жиыны ашық облыс болған жағдайда с1х2
5-сурет.
Бұл жағдайда мақсаттық функция максимал мәнге жетпейді.
Мақсаттық функция максимал (минимал) мәнге шығыс (кіріс) нүктесінде
Шектеу жүйесінің мәндер облысын координаттар жүйесінде көрсету, мақсаттық
Алдыңғы тараудың 1-есебінде мақсаттық функция z=1,2х1+х2 , ал
5х1+3х2 480
3х1+2х2 300
х1 0, х2 0
мұндағы 5х1+3х2 480 теңсіздігін а деп, ал
Мұнда алдымен шектеу жүйесінің АВСО көпбұрышын тұрғызамыз. Сонан
3х1+2х2=300
х1=0
теңдеулер жүйесінен табылады. Бүл жүйенің шешімі: х, =
Сонымен мақсат функциясының
4. Тасымалдау есебін шешу.
А1,А2,А3 үш станциясынан сәйкесінше а1,а2 ,а3 тонна жүгін
Кез келген Аi(i = 1,2,3) станциясының біреуінен
В1 В2 В3 В4
А1 с11 с12 с13 С14
А2 С21 с22 с23 с24
А4 с31 С32 с33 с34
1 - Кесте
(с шамасының 1-ші индексі жүк шығатын станцияның номері,
Бұл есепте келесі шарттар орындалатындай тасымалдау жоспарын құру
1) В1,В2,В3 және В4 пунктеріне
жеткізу;
А1,А2,А3 станцияларындағы жүкті түгелімен жеткізу;
жалпы тасымалдауға кететін шығындар аз жұмсалуы қажет.
Айталық ху(і = 1,2,3; / =
х11, х12, х13, х14, х21, х22, х23, х24,
Есептің берілгені мен белгісіздерді келесі кестеде көрсетейік:
Шығу станциялары Жүк салмағы Жеткізу пунктері мен жеткізуге
В1
b1 В2
b2 В3
b3 В4
b4
А1 а1 с11
х11 с12
х12 с13
х13 с14
х14
А2 а2 с21
х21 с22
х22 с23
х23 с24
х24
А3 а3 с31
х31 с32
х32 с33
х33 с34
х34
2-кесте
Сонда мақсат функциясы келесі түрде беріледі:
z 11х11+ 12х12+ 13х13+
қысқаша түрде:
Мақсат функциясы
Есептің мағынасына сәйкес хij 0
Осы жүйені қанағаттандыратын және мақсат функциясының мәнін ең
Тасымалдау есебінің шешу жолын 3 қадамда жүргіземіз.
2-ші кестедегі а1
жазайық:
Шығу станциялары Жүк салмағы Жеткізу пунктері мен жеткізуге
В1
300 В2
500 В3
100 В4
200
А1 100 с11
х11 с12
х12 с13
х13 с14
х14
А2 400 с21
х21 с22
х22 с23
х23 с24
х24
А3 600 с31
х31 с32
х32 с33
х33 с34
х34
3-кесте
1-қадам. Базистік шешімдерді табу.
хij тасымалдауларын табу үшін келесі әдісті қоладанайық. Ол
Нәтижесінде келесі 4-кестені аламыз:
Бұл жоспар бойынша А1,А2,А3 станцияларындағы барлық жүк В1,В2,В3
х11 = 100, х12 =0, х13 = 0,
мәндері қойылған есептің мүмкін мәндеріне жатады. Шығын мөлшері:
Ескерту. Торларды қоршау арқылы белгілеу жолымен алғашқы мүмкін
Қоршалған торлардың саны жол саны мен баған санының
Қолданған әдіс солтүстік-батыс бұрыш әдісі деп аталады. Шектеу
Торларда бос қалған белгісіздер (нөлге теңестірілген белгісіздер) бос
т + п-1 базистік белгісізі анықталған жүкті тасымалдаудың
2 - қадам. Базистік шешімдердің оптималдылығын зерттеу.
Айталық αi шамасы
болсын, ал βj шамасы Вj- жеткізу пунктіндегі 1
сij- жүкті тасымалдауға кететін шығын екені белгілі. Олай
жеткізу пунктіндегі бағасы оның бастапқы бағасы мен жеткізуге
Базистік шешімнің оптималдылық белгісі: егер базистік торлар
транспорттық есептің базистік шешімі оптималды болады.
Сонымен есептің базистік шешімін оптималдылыққа зерттеу үшін
Орындалатындай αi жэне βij (i =
бос тор үшін αi + сij
ең болмаса бір бос тор үшін бұл теңсіздік
онда бүл шешім оптималды болмайды, онда есепті шешудің
Аталған әрекеттерді мысалмен көрсетейік. Есептің кестесіндегі сij
шамаларына сандық мәндер берейік.
Енді базистік жоспарды оптималдылыққа зерттейік. α1 және βij
(А3,В4) базистік торы бойынша α3+с34 =β4 3+2=β4
Енді табылған мәндерді қоя отырып келесі кестені аламыз:
Енді бос торлар үшін αi +сij
(А1, В2) бос торы үшін теңсіздік орынды: 0
(А1,В3) бос торы үшін де теңсіздік орынды: 0
Ал (А1,В4) бос торы үшін: 0 + 1≺
z = 3.100 + 1.200 + 4 .
3 - қадам. Жаңа базистік шешімдерді анықтау.
(А1,В4) торына
7-кесте
(А1,В4) торына
7-кестеде Δ мәнін компенсациялау кезінде, қосу-азайту әрекеттерін горизонталь
мәні + таңбасымен жазылған базистік торларды қайта есептеу
Δмәні үлкен болған сайын мақсат функциясының да мәні
8-кесте
Бұл кестеде х11 = 0, сондықтан ол базистік
Қайта есептеуден кейін жаңа тасымалдау жоспарын құрдық:
х11 =0, х12 = 0, х13 =0, х14
х33 = 100, х34 =100
Мақсат функциясы жаңа мәнге ие болады:
z2 = 100 с14 + 300 с21 +
Бұл алдыңғы z1 = 2700 мәнінен аз.
Енді құрылған тасымалдау жоспарын оптималдылыққа зерттейміз. Мұны орындау
мәндерін анықтайық.
α1 = 0. (А1,В4) базистік торы бойынша α1
(А3, В4) базистік торы бойынша а3 + с34
(А3, В3) базистік торы бойынша а3 + с33
(А3,В2) базистікторы бойынша а3 +с32 = β2 ⇒
(А2, В2) базистік торы бойынша а2 + с22
(А2, В1) базистік торы бойынша а2 + с21
αi және βj. жаңа мәндерін келесі кестеге толтырамыз:
Енді бос торлар үшін αi+ сij
3-қадамды қайта
толтырамыз. (А2,В2) торына -∆, (А3,В2) торына +∆, (А3,В4)
анықталады:
10-кесте бойынша бос торлар үшін αi+ сij
тексерсек, оның барлық бос торлар үшін орындалатындығы шығады:
Олай болса
х11 = 0, х12 = 0, х13 =0,
шешімдері үшін мақсаттық функция минимал мән қабылдайды. Ол
тең
z= 1 . 100 + 1 . 300
Енді қорытындылайық. Тасымалдау әсептерін шешу үшін келесі әрекеттер
орындалады:
Алгашқы базистік шешімдер құрылады (1-қадам).
Алынган шешімдер оптималдылыққа
теңсіздігі тасымалдау
3. Егер αi+ сij βj
Онда жаңа базистік шешімдер құрылады. Бұл шешімдер
5. Тиімділік есебнің программасын құру және компьютер көмегімен
4-тарауда көрсетілген есептің программасын құрайық.
С0 = ║сij║ - тасымалдауға кетткен шығындардан құрылған
Тасымалдау жоспарының оптималды шешімін табуды сызықты программалаудың венгер
Берілген есепті шешуде итерацияны қолданамыз, ал шешудің алгоритмі
Алдымен ТШМ-ны белгілеп алу керек, бұл қадам итерацияның
Осы бағандарда ТМ-дағы ху ≠ 0 болатын мәндерге
ТМ -дағы аi ≠ 0 болатындай ТШМ-дағы жолдарды
1-қадам. ТШМ-дағы «-1» -мен белгіленген элементтерді қарастырудан алып
2-қадам. Есепті шешуді жалғастыруға қажетті, ТШМ-дегі қалған нөлдік
Бұл кезеңде ТШМ-да белгіленген элементтерді қарастырмайды. Қалған элементтерді
3-қадам. Бұл қадамда (2Қ) ТШМ-да тізбек құрылады. Бүл
2-қадамдағы ішкі программа төмендегідей құрылады. Жол бойынша байланыссыздық
Осылайша алынған Э = х ig min =
ТМ элементтерінен құрылған тізбекте олардың жұптығын анықтаймыз (Ғ(1/2)
Келесі кезеңде А және В векторларында «-1» таңбаларын
болса, онда есеп шешілген болып есептеледі, қорытынды ТМ
Unit Unit1;
Interface
uses
Windows, Messagea, SysUtils, Variants, Classes, Graphiecs, Controls, Forms,
Type
Tform 1=class (TForm)
РаnеІІ: ТРаnеІ;
SрееdВuttоn1: ТSрееdВuttоn;
SрееdВuttоn2: ТSрееdВuttоn;
SрееdВuttоn3: ТSрееdВuttоn;
SрееdВuttоn4: ТSрееdВuttоn;
Раnе12: ТРаnеІ;
StringGrid2:TStringGrid;
Раnе13: ТРаnеІ;
StringGrid1:TStringGrid;
StringGrid4:TStringGrid;
StringGrid3:TStringGrid;
GroupBox1:TGroupBox;
Edit2:TEdit;
Edit1:TEdit;
Label1:TLabel;
Label2:TLabel;
Label6:TLabel;
Procedure SpeedButton 1Click (Sender:TObject);
Procedure SpeedButton 4Click (Sender:TObject);
Procedure SpeedButton 2Click (Sender:TObject);
Procedure FromShow (Sender:TObject);
Procedure SpeedButton 3Click (Sender:TObject);
Procedure Edit2Change (Sender:TObject);
Procedure Edit1DblClick (Sender:TObject);
Private
{Ptivate declarations}
Public
{Ptivate declarations}
end;
var
Form1: TFrom1;
I,j,S,R,L:integer;
a:array[1..100] of inreger;
b:array[1..100] of inreger;
x:array[1..100,1..100] of inreger;
c:array[1..100,1..100] of inreger;
m,n:integer;
{$R*.dfm}
b[j]:= StrTolnt (StringGrid3.Cells[j,0]);
for i:=0 to m-1 do
for j:=0 to m-1 do
begin
c[j,i]:= StrTolnt (StringGrid1.Cells[j,0]);
end;
for i:=1 to m do
for j:=1 to n do
begin
x[I,j]:= StrTolnt (StringGrid2.Cells[j,0]);
end;
for i:=0 to m-1 do
begin
s:=0; r:=0;
for j:=0 to n-1 do
begin
s:=s+c[j,i];
end;
// if a[i]
«Экономика-математикалық моделдеу» пәніне оқыту
Тасымалдау есебін шешу
Сызықтық программалаудың негізгі есебі
Экономикалық математикалық модельдердің даму тарихы
ШАҒЫН ЖӘНЕ ОРТА БИЗНЕСТІҢ ТЕОРИЯЛЫҚ АСПЕКТІЛЕРІ
Инвестициялық жоба тиімділігін басқару
Симплекс әдісі және оның қолданылу алгоритмі
Қазақстан Республикасы мемлекеттік жалпыға міндетті білім беру стандарты
Параметрлік программалау есептері
Экономика-математикалық модельдеу – жүйелік экономикалық анализдің методологиялық базасы