Сызықтық бағдарламалаудың жалпы есебі және математикалық бағдарламалау есептерініңмодельдерін құру
Жасанды базисті симплекс әдісі (М-әдіс)
жүктеу/скачать 147,42 Kb.
|
1 Сызықтық бағдарламалау
СӨЖ 1 САРЫМСАҚ,К 205 19 Ғ ӘДЕБИЕТІ, СӨЖ 2 САРЫМСАҚ.К 205 ӘДЕБИЕТ ТЕОРИЯСЫ
- Бұл бет үшін навигация:
- 1.5 Сызықтық бағдарламалау есептерін Excel ортасында Поиск решения қондырмасының көмегімен шешу
- 1.6 Сызықтық бағдарламалау әдістерімен шешілетін есептердің класстары мен мысалдары
| 1.4 Жасанды базисті симплекс әдісі (М-әдіс)
Сызықтық бағдарламалаудың бастапқы канондық есебінде (СБКЕ) бастапқы тірек жоспары жоқ болғанда жасанды базисті симплекс әдісі қолданылады.Мұндай жағдай бастапқы шектеуде «тең» немесе «үлкен немесе тең» деген таңбалары болғанда орын алады. М-әдіс М-есебіне симплекс-әдісін қолдаудан тұрады. Ол бастпақы есепке бастапқы СБКЕ теңдеулер жүйесінің сол жағына жаңадан алынатын матрица сызықтық тәуелді емес бірлік векторларының жүйесінен тұратындай тиісті теріс емес жасанды айнымалылары бар жасанды бірлік векторларын қосудан құралады. Бастапқы есептің мақсатты функциясына оның максималдануы кезінде жасанды айнымалылардың қосындысына (-М) саны көбейтілген түріндегі қосылғыш қосылады, мұндағы М – жеткілікті үлкен оң сан, яғни базистен осы айнымалыларды алу үшін оларды мақсатты функцияға (-М) үлкен теріс коэффициенттерімен енгізеді. Осылайша алынған есепте бастапқы тірек жоспары белгілі. М-есебін шешу барысында симплекс-кестесінде жасанды векторларды олардың базистен шығуына байланысты сызып отыру керек. Егер жасанды векторлардың барлығы базистен шықса, онда бастапқы есептің теңдеулер жүйесіне ұқсас теңдеулер жүйесін аламыз. Егер М-есептің оңтайлы шешімінде жасанды айнымалылар болса және М-есебі шешілмейтін болса, онда бастапқы есеп те шешілмейді. Мысалы. Симплекс әдісімен сызықтық бағдарламалау есебін шешу: f(Х)=3х1+3 х2→ max шектеулері: Канондық формасы: f(Х)=3х1+3 х2+0х3+0х4+0х5 → max шектеулері: Шектеулер жүйесінде ішкі бірлік матрицасы жоқ. СБКЕ бастапқы тірек жоспары жоқ. Тірек жоспарын табу үшін М-есебіне көшеміз: f (Х)=3х1+3 х2+0х3+0х4+0х5-Му → max шектеулері: Бастапқы (нольдік) 1.7 Х(0)=(0;0;8;0;2;1) симплекс кестесін құрайық. Бастапқы кестедегі (-2М-3)-ге тең ең кіші Δj мәні базиске енгізілетін векторына сәйкес келеді, ал жасанды Р векторы базистен шығарылады, өйткені оған ең кіші R min=0,5 сәйкес келеді. Р сәйкес келетін бағана келесі симплекстік кестелерден сызылады. Бірінші симплекс кестесінде жаңа Х(1)= (0,5;0;7,5;0;1,5) тірек жоспары алынды, ол бастапқы есептің тірек жоспары болса да, оңтайлы болып табылмайды, өйткені симплекстік кестенің 4-ші жолында (кесте 1.7) екі теріс симплекс-айырмасы (-4,5 және -1,5) бар. Ең кіші симплекс-айырма векторына сәйкес келеді. Бұл алынған жоспар оңтайлы емсе екендігін білдіреді және оны базиске векторын енгізу арқылы жақсартуға болады. Екінші симплекс кестесінде бастапқы есептің Х(2)= (3; 5; 0; 0; 9) оңтайлы жоспары алынды, себебі Δj ≥0. Мақсатты функцияның максимал мәні f(X) = 24. Алайда симплекстік кестенің соңғы жолының анализі базиске енбеген векторына нольдік симплекс-айырмасы сәйкес келетінін көрсетеді. векторын базиске енгізуге болады, бірақ мақсатты функцияның мәні ол кезде өзгермейді. Кесте 1.7
Енді бір итерацияны орындайық: базиске орнына енгізейік. Есептеулер нәтижесі 1.8 кестесінде көрсетілген. Кесте 1.8
Үшінші симплекстік кестеде бастапқы есептің тағы бір Х(3) =(6;2;0;9;0) оңтайлы жоспары алынған және мақсатты функцияның максимал мәні f(X) = 24. Жауабы. Екі оңтайлы жоспар алынған: Х(2)= (3; 5; 0; 0; 9)жәнеХ(3) =(6;2;0;9;0); f(X) = 24. 1.5 Сызықтық бағдарламалау есептерін Excel ортасында Поиск решения қондырмасының көмегімен шешу Поиск решения – бұл оңтайлы есептерді шешуге көмектесетін Excel қондырмасы. Поиск решения диалогтық терезесінде негізгі параметрлері: шектеулер ұяшықтарын өзгерте отырп, мақсатты ұяшықты белгілеу. Есепті шешу үшін: шешім нәтижесі жазылатын ұяшықтар адресін көрсету (өзгертілетін ұяшықтарды көрсету); бастапқы мәліметтерді енгізу; мақсатты функцияның тәуелділіктерін енгізу; шектеулер үшін тәуелділіктерді енгізу; «Поиск решения» командасын іске қосу; Мақсатты функция үшін ұяшықты белгілеу (мақсатты ұяшықты белгілеу); Шектеулерді енгізу; СБЕ есептерін шешу үшін параметрлерді енгізу. Поиск решения командасын қосу. Мақсатты функция үшін ұяшықты белгілеу. Поиск решения терезесінің элементтерінің мағынасын түсіндірейік. Мақсатты ұяшықты белгілеу – мәнін максималдандыру, немесе минималдандыру, немесе нақты бір мәнге теңестіруді қажет ететін мақсатты ұяшықты анықтайды. Мұнда мақсатты функция жазылған ұяшықтың адресін енгізу керек. Ұяшықтың адресін $С$3 енгізіңіз. Есептің шартына байланысты мақсатты функцияның түрін енгізіңіз. Ол үшін мақсатты функция максимал немесе минимал мәнге тең бе, соны анықтау керек. Изменяя ячейки – өзгертілетін ұяшықтарды анықтайды. Өзгертілетін ұяшық – бұл шешімді табу барысында қажетті нәтижеге жету үшін өзгертілуі мүмкін ұяшық. Өзгертілетін ұяшықтардың санын 200-ге дейін қоюға болады. Ізделінетін айнымалылардың адрестерін $А$2:$В$2 енгізіңіз. Предположить – «Установить целевую ячейку» терезесіндегі формулаға тура немесе жанама тәуелділігі бар барлық формуласыз ұяшықтарды тауып, «Изменяя ячейки» терезесіндегі сілтемелерге орналастырылады. Ограничения – берілген есептің ағымдағы шектеулерін тізбектейді. Добавить – берілген есепке шектеулерді қосуға болатын «Добавление ограничения» диалогтық терезесін шығарады. Изменить – берілген шектеулерді өзгертуге болатын «Изменение ограничения» диалогтық терезесін шақырады. Удалить – белгіленген шектеуді жояды. 7. Шектеулерді енгізу. «Добавить» пернесіне бағдар. Ссылка на ячейку – мәндері шектелетін ұяшықты немесе ұяшықтардың интервалын анықтайды. Ограничение — «Ссылка на ячейку» терезесінің құрамына қойылатын шартты анықтайды. Ссылка на ячейку жолында $С$4 адресін енгізіңіз. Введите знак ограничения:ұяшық (немесе интервал) және тізімнің оң жағындағы терезеде енгізілетін шектеудің арасындағы қатынасты тізімнен таңдап енгізіңіз. Ограничение жолында $D$4 адресін енгізіңіз. Содан кейін «Добавить» және қалған шектеулерді жоғарыда келтірілген алгоритм бойынша енгізу қажет. 8.Сызықтық бағдарламалау есебін шешу үшін параметрлерді енгізу. Поиск решения диалогтық терезесінде тышқан бағдарын Параметры пернесіне қойыңыз. Осы терезедегі командалардың көмегімен оңтайландыру есептерінің барлық класстарын шешуге қажеттішарттарды енгізуге болады. Сызықтық және сызықтық емес есептердің параметрлерін анықтауға болады. Диалогтық терезедегі параметрлердің әрқайсысы көптеген есептерге келетін бастапқы әдепкі (по умолчанию) мәнге ие. Максимальное время – есептің шешімін табуға берілетін уақытты шектеуге арналған. Мұнда 32767 аспайтын уақытты (секундпен) енгізуге болады; 100 мәні әдепте қойылып, көптеген қарапайым есептерге келеді. Предельное число итераций – шешімді табуға кететін уақытты итерациялар санын шектеу жолымен шектейді. Бұл мән 32767 дейінгі бүтін оң сан болу керек. Относительная погрешность – шешімді табу кезіндегі шешімнің дәлдігін орнатады. Мұнда енгізілетін сан «Ограничение» ұяшығының мәні қажетті теңдікті қанағаттандыратынын немесе белгіленген шекараларда табылатынын анықтау кезінде қолданылады; 0 мен 1 арасындағы бөлшек сан болуы керек (шеттерін санамағанда); әдепкі мәні 0,000001 тең; егер сан бөлшектері кіші болса (мысалы, 0,0001), онда кіші дәлдікті көрсетеді. Неғұрлым жоғары дәлдік (сан кіші болған сайын) анықталса, шешімді табуға соғұрлым көп уақыт қажет етіледі. Допустимое отклонение – өзгертілетін ұяшықтар бүтін сандар жиынымен берілгенде оңтайлы шешімнен ауытқитын шаманы енгізу үшін қолданылады.Ауытқу неғұрлым үлкен болса (мүмкін болатын ауытқу процентпен), шешу барысы соғұрлым тез болады. Бүтінсанды шектеулер берілмесе, ауытқуларды енгізудің мағынасы жоқ. Сходимость – сызықтық емес есептерге ғана қолданылады. Мақсатты ұяшықтағы мәннің салыстырмалы өзгеруі соңғы бес итерацияда Сходимость жолындағы көрсетілген саннан кіші болғанда, іздеу тоқтатылады. Параметр 0 мен 1 арасындағы мәндерді қабылдайды. Жақсы жинақтылықты неғұрлым көп ондық таңбалар сипаттайды, мысалы: 0,0001 салыстырмалы өзгерімі 0,01 қарағанда кіші. Жақсы жинақтылық оңтайлы шешімді табуғу көбірек уақытты қажет етеді. Линейная модель – шешімді табу барысын тездетеді. Бұл команда барлық байланыстар сызықтық болғанда ғана қолданылады. Показывать результаты итераций – шешімді табуды үзіп, әр итерациядан кейін нәтижелерді көрсетеді. Автоматическое масштабирование –автоматты масштабты қосады. Бұл енгізу (Изменяя ячейки) және шығару (Установить целевую ячейку және Ограничения) параметрлері шамалары бойынша қатты өзгешеленгенде пайдалы; мысалы, кірісті максимизациялау процентпен және миллион тенгемен есептелетін қаржы жұмсау. Оценки –әр бірөлшемді іздеуде негізгі айнымалылардың бастапқы бағаларын алу үшін қолданылатын тәсіл: линейная – жанама вектордың бойындағы сызықтық экстраполяцияны қолданады; квадратичная – квадраттық экстарполяцияны қолданады. Разности –мақсатты және шектейтін функциялардың дербес туындыларын бағалау кезіндегі туындыны есептеу тәсілі: прямые – әдепкіде осы дифференциалдау тәсілі қойылған; центральные –жұмыс бетінде көбірек есептеуді қажет етеді, бірақ Поиск решения шешімді жақсарта алмайтыны туралы хабарлама алынған жағдайларда, көмектесуі мүмкін. Метод поиска –әр итерацияда қандай алгоритм қолданылатынын анықтайды. Әдістердің бірін көрсету керек: Ньютон –өздігінен қойылған; сопряженного градиента –Ньютон әдісіне қарағанда азрақ жадыны, бірақ нақты дәлдікке жету үшін әдетте көбірек итерациянықажет етеді. Егер есептеулер көлемі өте көп және жадыны үнемді пайдалану маңызды болса, осы әдісті қолданған дұрыс. Загрузить модель –Загрузить модель диалогтық терезесін шығарады, онда үлгінін қайсысын қолдануды көрсетуге болады. Сохранить модель –Сохранить модель диалогтық терезесін шығарады, онда таңдаған үлгіні қай жерде сақтауға болатынын көрсетеді. Сохранить модель пернесін тек біреуден артық Поиск решения үлгісі берілген жұмыс бетімен сақтайтын жағдайда қолдану керек.Поиск решения бірінші үлгісі жұмыс бетімен бірге автоматты түрде сақталады. Линейная модель (бұл симплекс әдісті қолдануды қамтамасыз етеді) және Неотрицательные значения терезелерінде жалаушаларды қосыңыз. Тышқан сілтеуішін ОК пернесіне қойыңыз. Экранда Поиск решения диалогтық терезесі шығады. Тышқан сілтеуішін Выполнить пернесіне қойыңыз. Шешімді іздеу нәтижелері және t мәндері мен мақсатты функцияның максимал мәні жазылған СЗ ұяшығы үшін АЗ:ВЗ толтырылған ұшықтары бар бастапқы кесте. Результаты поиска решения диалогтық терезесі қажетті шешімге ең жақын ұяшықтардың мәндерін қолданып, соңғы есептеудің нәтижелерін шығарады. Поиск решения шешімді іздеу әрекеттерін тоқтатқан кезде, Результаты поиска диалогтық терезесінің жоғарғы жағында біткені туралы хабарлама беріледі. Ерекше жағдайлар: 1) «Значения целевой ячейки не сходятся» хабарламасы алынды. Бұл хабарлама мақсатты функция шектелмеген жағдайда беріледі. 2) «Поиск не может найти подходящего решения»хабарламасы алынды. Мұндай хабарлама шектеулер жүйесінің бірлеспеген жағдайында көрсетіледі. 1.6 Сызықтық бағдарламалау әдістерімен шешілетін есептердің класстары мен мысалдары Өндірісті жоспарлау есебі (ресурстарды оңтайлы қолдану). Мысалы. А, В және С бұйымдарын жасау үшін акционерлік қоғам 1, 2 және 3 үш әр түрлі қорларды қолданады. А бұймының бір бірлігін, Вбұймының бір бірлігін, С бұймының бір бірлігін шығару үшін 1-ші қордың пайдалану нормалары сәйкесінше 18, 15 и 12 кг;2-ші қордың пайдалану нормалары А, В және С бұйымдарын шығару үшін -6, 4 және 8кг; 3-ші қор үшін -5, 3 және3 кг. А, В және С бұйымдарының бір данасын өткізу кірісі сәйкесінше 9, 10 және 16 мың тенгені құрайды. Бұйымдар кез-келген мөлшерде шығарылуы мүмкін, себебі өткізу қамтамасыз етілген. Алайда, олардың шығарылуы осы уақыттағы бар әр қордың жалпы мөлшерімен шектеледі, бірінші қор түрінің жалпы мөлшері 360кг, екіншісі – 192кг, үшіншісі – 180кг құрайды. Өндірістік АҚ жалпы кірісі ең көп болатын А, В және С бұймдарының шығару жоспарын құру керек. Бастапқы мәліметтерді 1.10 кестесіне енгізуге болады. Кесте 1.10
Математикалық үлгі. Айнымалылар: х1- А бұйымының саны (шт); х2 –В бұйымының саны (шт), х3 –С бұйымының саны (шт). Мақсатты функция: f (х1, х2, х3)=9х1+10х2+16х3 → max Шектеулер: Мысалы. 1 мысалдың шарты бойынша өнімді өткізуде қиындықтар бар. Өнеркәсіп жоспар бойынша А бұйымының 5, В бұйымының 7, С бұйымының 18 данасынан кем емес шығаруға міндетті. Жоспар артығымен орындалуы мүмкін, бірақ белгілі бір шектеулермен, сұраныс шарты әр түрлі шығарылатын даналардың санын шектейді: 8, 15, 22 бірліктен аспауы керек. Өндірісті жоспар орындалатындай немесе артығымен орындалатындай , ал жалпы кіріс максимумге айналатындай қылып жоспарлау керек. Математикалық үлгі. х1- А бұйымының саны (шт); х2 –В бұйымының саны (шт), х3 –С бұйымының саны (шт). Мақсатты функция: f (х1, х2, х3)=9х1+10х2+16х3 → max Шектеулер: Мысалы. Қордың 100 данасы және 2 жоба бар. Бірінші жоба бойынша салынған қаржының бір бірлігіне қайтарым 1,8; екінші жобада -1,4. Бірінші жобаның сәтті аяқталу ықтималдылығы 0,85, екінші жобанікі – 0,95. Күтілетін пайда максимал болатындай инвестицияларды жобалардың арасында бөлу керек. Ресурстар бар мөлшерінен артық пайдаланбайтындай, ал күтілетін жоғалтулар бар ресурстың 9% артық болмауы керек. Математикалық үлгі. Айнымалылар: х1- бірінші жобаға салынған инвестициялар мөлшері; х2 – екінші жобаға салынған инвестициялар мөлшері. Мақсатты функция: f (х1, х2)=1,8∙ 0,85х1+1,4∙ 0,95х2 → max Шектеулер: Қоспа туралы есеп. Мысалы. Металлургиялық зауытқа құрамында 0,03% аспайтын фосфоры және 3,25% аспайтын күлдің қоспалары бар көмір қажет. Зауыт құрамындағы қоспалары белгілі А, В және С сортты көмірді сатып алады. Нәтижесіндегі қоспа құрамындағы қоспағы (примесь) бойынша шектеулерді қанағаттандыратын және минималды бағаға ие болатындай бастапқы А, В, С өнімдерін қандай пропорцияда араластыру керек. Қоспаның құрамы мен бастапқы өнімдердің бағасы 1.11 кестесінде көрсетілген. Кесте 1.11
Математикалық үлгі. Айнымалылар: х1 – тонна қоспада А сортты көмірдің мөлшері, х2 - тонна қоспада В сортты көмірдің мөлшері, х3 -тонна қоспада С сортты көмірдің мөлшері. Мақсатты функция: f (Х)=30х1+ 30х2+45х3 → min Шектеулер: Мысал. Құс шаруашылық ферманың бройлер шаруашылығы 20000 балапандарды құрайды, олар 8-жұмалық жасқа дейін өсіріледі және тиісті өңдеуден кейін сатылымға шығарылады. Бір балапанға кететін жемнің жұмалық шығыны орташа (8 жұмада) 500 граммды (0,5 кг) құрайды. Балапандардың 8-ші жұмаға қажетті салмаққа жету үшін жемшөп рационы нәрлік бойынша белгілі талаптарды қанағаттандыру керек. Мұндай талаптарға жемнің әртүрлі қоспалары немесе ингредиенттері лайық бола алады. 1.12 кестеде әр ингредиентта нәрлі заттардың құрамын (салмақ бойынша) және әрбір ингредиенттің меншікті бағасын сипаттайтын мәліметтер көрсетілген.Қоспаның жалпы салмағынан қоспада қальцийдің 0,8% кем, аққуыздың 22% кем, өзектің 5% көп емес болу керек. Қоспаның минималды бағасын құрайтын әр үш ингредиенттің керекті килограмм санын табу керек. Жем қоспаның жалпы шығынына және оның нәрлігіне қойылатын талаптарды сақтау кезінде. Кесте1.12
Математикалық үлгі. Айнымалылар: х1 – қоспада әктастың құрамы (кг), х2 –қоспада астықтың құрамы(кг), х3 –қоспада соя бұршақтың құрамы(кг). Апта сайын балапдардың қоректенуге кететін қоспаның жалпы салмағы 20000·0,5=10000кг, кальцийдің қоспадағы мөлшері – 0,008·10000=80кг кем емес, аққуыздың қоспадағы мөлшері – 0,22·10000=2200кг кем емес, өзектің қоспадағы мөлшері - 0,05·10000=500кг көп емес. Мақсатты функция: f (Х)=0,04х1+0,15х2+0,40х3 → min Шектеулер: Жабдықтарды жүктеу туралы есеп (қаутты пайдалану туралы) Мысал. Тігін фабрикада екі түрлі станок бар, олардың 12 станогы 1-типті және 9 станок 2-типті. Станоктар үш түрлі маталарды шығарады: Т1, Т2, Т3, бірақ әртүрлі өнімділікпен. Станоктардың өнімділігі туралы мәліметтер 1.13 кесте көрсетілген. Т1 бұлдың әрбір метрі фабрикаға 15 ш.б. пайданы әкеледі, Т2 түрлі – 23 ш.б., Т3 – 13 ш.б. Кесте1.13
Фабрикаға белгіленген жоспар бойынша айына Т1 матаның 180 метрден, Т2 матаның 270 метрден, Т3 матаның 310 метрден кем шығармау керек; әртүрлі матаның метрлер саны сәйкес 200, 300, 350 метрлерден аспау керек. Барлық станоктар жүктелу керек. Жиынтық айлық пайда максималды болатын Т1, Т2, Т3 маталарды шығаратын станоктардың жүктелуін үлестіру керек. Математикалық үлгі. Айнымалылар: х11- Т1матаны шығаратын 1-типті станоктар саны; х12 – Т2 матаны шығаратын 1-типті станоктар саны; х13 – Т3 матаны шығаратын 1-типті станоктар саны; х21- Т1 матаны шығаратын 2-типті станоктар саны Т2матаны шығаратын 2-типті станоктар саны; х23 –Т3матаны шығаратын 2-типті станоктар саны. Мақсатты функция: f (Х)=15(4х11+3х21)+23(6х12+5х22)+13(8х13+7х23 )→ max Жоспарды орындау бойынша шектеулер: . Жоспарды асыра орындау бойынша шектеулер: . Жабықтың болуы және оны толық жүктелуі бойынша шектеулер: Шикізатпен жабдықтау туралы есеп. Мысал. А1, А2 және А3 үш жанармайқоймаларда (жіберу пункттері ЖП) сәкесінше 100, 130, және 170 т жанармай бар. Жанармай АҚС1, АҚС2, АҚС3 және АҚС4 төрт автоқұю станцияларына (тағайындалу пункттері ТП) жеткізіледі, олар сәйкесінше 150, 120, 80 және 50т жанармайға сұраныс жіберді. i-ші Аi қоймадан j-ші АҚСj біртекті түрлі транспортпен жанармайды тасымалдау құны белгілі, ол 1 т жанармай үшін сij ақшалай бірлікті құрайды Трнспорттық шығындар матрицасы келесі түрде болады: С= Барлық тасымаулардың жалпы жиынтық бағасы минималды болатын хij (i=1,2,3 j=1.2.3,4) оңтайлы тасымалдау жоспарын табу керек. Математикалық үлгі. Айнымалылар: х11- х14 – А1 жанармайқоймадан барлық АҚС (1-4) тасымалданатын жанармай мөлшері тонна; х21 – х24 – А2 жанармайқоймадан барлық АҚС (1-4) тасымалданатын жанармай мөлшері тонна; х31 – х34 –А3 жанармайқоймадан барлық АҚС (1-4) тасымалданатын жанармай мөлшері тонна. Мақсатты функция: f (Х)=3х11+5х12+7х13+11х14+х21+4х21 +6х23+3х33+ 5х31+ +8х32+ 12х33+7х34 → min Жеткізушілер бойынша шектеулер: Тұтынушылар бойынша шектеулер: Материалды оңтайлы пішу есебі Мысал. Имеются прутки одинаковой длины, из которых нужно нарезать определенное количество заготовок заданной длины. Прутки можно нарезать на заготовки в различных сочетаниях. При каждом варианте нарезания прутков остаются концевые отрезки. Требуется определить, какое количество прутков следует разрезать по каждому варианту, чтобы получить заданное количество заготовок различной длины и чтобы общая длина концевых отрезков была минимальной. Есептің берілгендерін 1,14 кесте түрінде көрсетуге болады. Кесте 1.14
Белгілерді түсіндірейік: i – номер вида заготовки, i= ; j –номер варианта раскроя прутка, j= ; аij – количество заготовок i-го вида, получаемого из одного прутка, разрезаемого по j-му варианту; bi – требуемое число заготовок i-го вида; cj – длина концевого остатка, оставшегося от одного прутка при разрезании прутка по j-му варианту. Математикалық үлгі. Айнымалылар: х1, х2, …, хj, …, хn – план раскроя прутков, где хj – число прутков, разрезаемых по j-му варианту, j= ; Мақсатты функция: f (Х)=с1х1+с2х2+…+ cn хn= , где с1х1 – общая длина концевых отрезков от х1 прутков, разрезанных по первому варианту, общая длина концевых отрезков от х2 прутков, разрезанных по второму варианту, будет равна с2х2 и т.д. Ограничения по заготовкам: хj ≥0, i= ; j= . Мысал. Қағаз фирманың өнімі стандартты ені 2 метр қағаз рулондар түрінде шығарылады. Тұтынушылардың арнайы тапсырыстары бойынша фирма басқа да өлшемді рулондарды шығарады, ол үшін стандартты рулондар кесіледі. Стандартты емес өлшемді рулондар ға тапсырыс және стандартты емес рулондарды істеу Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины – по 2 метра. По специальным заказам потребителей фирма поставляет рулоны и других размеров, для чего производит разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров и ограничения, связанные с требованием обеспечить изготовление требуемого количества нестандартных рулонов приведены в таблице 1.15. Кесте 1.15
Требуется найти такие сочетания различных вариантов разрезания стандартных рулонов, чтобы поступившие заказы полностью удовлетворить с минимальными потерями (отходами). Математикалық үлгі. Айнымалылар: хj – j-шінұсқа бойынша қиылатын стандартты рулондар саны, j= ; барлығы х1, х2, х3, х4, х5, х6 . Мақсатты функция: жиынтық шығындарды анықтайтын f(Х)=0,4х1+0,3х2+0,1х3+0,1х5+0,2х6→min. Рулондар саны бойынша шектеулер: жүктеу/скачать 147,42 Kb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||