Simplex algoritmo

Matematikan, simplex algoritmoa programazio linealeko ebazkizunak aztertu eta ebazteko metodo bat da. Programazio linealeko metodoak helburuko funtzio linealak, murrizketa linealekin batera, optimizatzeko erabiltzen dira. Hobezina edo optimoa murrizketek osatzen duten eskualde egingarriko eremuan aurkitu behar denez, simplex algoritmoak erpin hauetan zehar egiten du soluzioaren bilaketa, ondoko erpin batera aldatzeak helburu funtzioaren balioren hobekuntza dakarren egiaztatuz. Erpinaren aldaketak soluzio hobea ekartzen ez badu, aztertzen ari den erpina hobezina izango da. Simplex algoritmoa George Dantzig matematikariak garatu zuen 1947 urtean.

Ebazkizuna

Programazio linealeko ebazkizun bat helburuko funtzio bat, zenbait aldagairen mendean, eta aldagai horiek har ditzaketen balioei buruz murrizketa linealak, desberdintza moduan adierazita. Ohikoak aldagaiei buruzko ez-negatibotasun baldintzak. Murrizketek aldagaiek har ditzaketen balioez osaturiko eskualde egingarri bat definitzen dute. Helburuko funtzioa hoberenatu (maximizatu edo minimizatu) egiten duten aldagaien balioak edo hobezina eskualde egingarriko erpin batean kokatzen da eskualde egingarria politopo konbexu bat osatzen duenean. Eskualde egingarria bornatua ez denean, baliteke hobezina mugatua ez izatea.

Oro har, horrela planteatzen da ebazkizuna modu kanonikoan:


murrizketa hauekin


Simplex algoritmoa garatzeko, alegiazko aldagai izenekoak sortzen dira, zuzenean esanahirik ez dutenak, horiek gehitu edo kenduta murrizketak ezartzen dituzten desberdintzak berdintza bihurtu eta ebazkizuna modu estandarrean adierazteko. Handiago edo berdin motako murrizketak, (-1) balioaz biderkatzen dira, txikiago edo berdin motako murrizketa bihurtzeko. Adibidez:




Ebazkizunak minimizatzea eskatzen duenean, maximizatze-ebazkizun bihurtzen da modu honetan:


Adibidea

Minimizatze ebazkizuna baten bihurketa eta alegiazko aldagaien sorrera adibide honetan ikus daitezke:

murrizketa hauekin

murrizketa hauekin

Simplex algoritmoa

Simplex algoritmoa taulaz taula garatu ohi da, taula bakoitzean balizko soluzio baten balorazio egin eta taula batetik bestera aldagai bat atera eta beste aldagai bat sartuz. Taula bateko balizko soluzioan parte hartzen duten aldagaien aldagai basiko deritze.

Adibide gisa, programazio linealeko ebazkizun hau planteatzen da:


murrizketa hauekin


.


Alegiazko aldagaiak sortuz:


murrizketa hauekin



Abiapuntu gisa, eskualde egingarriko edozein erpin har daiteke. Kalkulu gehigarririk ez egiteko, eskualde egingarrian izaten den (x1=0, x2=0) puntutik has daiteke. Lehenengo taula honela eratzen da:


1. taula
cB B basea cj Konstanteak Ratioak
5 8 0 0
x1 x2 x3 x4
0 x3 1 2 1 0 100 100/2=50
0 x4 6 3 0 1 300 300/3=100
cj-zj 5-1×0-4×0=5 8-6×0-3×0=8 0-1×0-0×0=0 0-0×0-0×0=0 Z=0


Taulan murrizketa adina lerro osatzen dira. Lehenengo cB zutabean, aldagai basikoek helburuko funtzioan dituzten koefizienteak jartzen dira. Koefiziente hauek aldagai guztiak agertzen diren lerroaren gainean ere agertzen dira lagungarri gisa. Bigarren zutabean aldagai basikoak (baloratzen ari den soluzioan agertzen diren aldagaiak) agertzen dira. Ondorengo zutabeetan, murrizketetako koefizienteak agertzen dira aldagai guztietarako. Balio hauek guztiak jarri ondoren, basikoak ez diren aldagaietan sartu beharrekoa zein den erabaki behar da.

Horretarako, aldagai guztiek unitate gehigarri bakoitzeko helburuko funtzioa dakartzaten ekarpenak (cj-zj) kalkulatu behar dira, taulan erakutsi bezala, azken lerroan. Ekarpen positibo handiena dakarrena sartzen da basean. Beraz, lehenengo taula honetan x2 aldagaia sartu behar da basean.

Hurrengo pausoan, basetik zein aldagai atera behar den erabaki behar da. Horretarako, ratioak izeneko azken zutabea eratu behar da. Zutabe hau konstanteen zutabea zati, murrizketa-matrizean, basera sartu behar den aldagaiaren koefizienteen zutabea eginez kalkulatzen da. Kasu honetan, x2 aldagaia sartu behar denez, murrizketa-matrizeko bigarren zutabeko koefizienteak hartzen dira (2 eta 3). Ratio txikiena duen aldagaia atera behar da, murrizketa-matrizeko koefizientea positiboa den guztietan: kasu honetan, x3 baztertu behar da.

Jarraian bigarren taula osatu behar da. Horretarako gontz-eragiketa izenekoa garatu behar da. Pibota sartu behar den aldagaiaren zutabean eta atera behar den aldagaiaren errenkadan dagoen zenbakia da. gontz hori 1 bihurtu behar da eta bere zutabeko beste balio guztiak 0 bihurtu behar dira. Bihurketa hauek Gauss-Jordan algoritmoa erabiliz egiten dira: gontza 1 bihurtzeko bere lerroko koefiziente guztiak, konstanteak barne, gontzaren balioaz zatitu behar dira; bere zutabeko elementu guztiak 0 bihurtzeko, pibotaren lerroa konstante batez biderkatu eta beste lerroak gehitu behar dira. Honako bigarren taula honetan, lehenengo lerroa lehenengo taulako lehenengo lerroa zati 2 da; bigarren lerroa lehenengo taulako lehenengo bider (-3/2) gehi bigarren lerroa da.

2. taula
cB B basea cj Konstanteak Ratioak
5 8 0 0
x1 x2 x3 x4
8 x2 1/2 1 1/2 0 50 50/(1/2)=100
0 x4 9/2 0 -3/2 1 150 150/(9/2)=22.22
cj-zj 5-(1/2)×8-(9/2)×0=1 8-1×8-0×0=0 0-(1/2)×8-(-3/2)×0=-4 0-0×8-1×0=0 Z=400


Bigarren taula osaturik, x4 aldagaia atera eta x1 aldagaia sartu behar da. Honako hirugarren taula honetan, Gauss Jordan algoritmoari jarraiki, bigarren lerroa aurreko bigarren lerroa bider (2/9) da; bigarren lerroa aurreko bigarren lerroa bider (-1/9) gehi aurreko lehenengo lerroa da.


3. taula
cB B basea cj Konstanteak Ratioak
5 8 0 0
x1 x2 x3 x4
8 x2 0 1 4/6 -1/9 33.33 -
5 x1 1 0 -3/9 2/9 33.33 -
cj-zj 5-0×8-5×1=5 8-1×8-0×0=0 0-(4/6)×8-(-3/9)×5=-66/18 0- (-1/9)×8-(2/9)×5=-2/9 Z=433.33


x1 eta x2 aldagaiak basean daudelarik, aldagai guztien ekarpenak negatiboak edo 0 direnez, ez da ezer irabazten aldagai berriak sartzean. Beraz, soluzio optimora heldu da: x1=33.33 eta x2=33.33, horrela helburuko funtzioan 5x1+8x2=433.33 lortuz.

Simplex algoritmo berrikusia

Jatorrizko simplex algoritmoaren bertsio ezberdinak garatu dira. Horietako bat simplex algoritmo berrikusia da, programazio linealeko ebazkizun handietan (hainbat aldagai eta murrizketa dutenetan, alegia) konputazio-lna txikiagoa eskatzen duena hobezin edo optimora heltzeko. Algoritmoaren bertsio berrikusi hau da, gainera, programazio linealeko softwarean erabili ohi dena.

Simplex algoritmo duala

Simplex algoritmoa eskualde egingarriko erpin batetik bestera mugitzen da, aldi bakoitzean soluzio hobetuz, harik eta hobezinera heldu arte. Hau da, simplex metodoan egingarritasuna ziurtatuz, hobezintasuna bilatzen da. Simplex algoritmo dualaren bitartez, berriz, hobezintasuna ziurtaturik, egingarritasuna bilatzen da, hau da, egingarria ez den soluzio hobezin batetik abiatzen da, pausoz pauso egingarritasunera joaz.

Aplikazio orokorra duen metodoa erabiltzen da, baina bereziki erabiltzen da abiapuntuko murrizketa matrizeko alde konstantean balio guztiak negatiboak direnean (murrizketak handiago edo berdin motakoak direnean gertatzen da hau), kasu horretan simplex metodo estandarra ezin baita aurrera eraman. Izan ere, aldagaien soluzio-balioak ematen dituen konstanteen zutabea negatiboa denean, soluzioa negatiboa da eta ez egingarria da, aurrez aldagaien ez-negatibotasun murrizketak ezarri direlako.

Abiapuntua simplex algoritmo estandarreko lehenengo taula da. Bertatik balio txikiena duen aldagai basikoa basetik ateratzen da. Sartu beharreko aldagaia zein den erabakitzeko, cj-zj zutabeko balioak basetik ateratako aldagairen lerroko koefiziente negatiboez zatitu eta bertatik txikiena ematen duen aldagaia hartzen da. Lerroko koefiziente guztiak positiboak edo 0 badira, ebazkizunak ez du soluzio egingarririk.

Taula batetik bestera aldatzeko, Gauss-Jordan aldakuntzak egiten dira, sinplex algoritmo estandarrean bezala. Soluzio hobezinera aldagai basikoen balio guztiak positiboak edo 0 direnean heltzen da.

Kanpo estekak

Read other articles:

Indian politician Basavaraj Patil SedamMember of ParliamentRajya SabhaIn office3 April 2012 – 2 April 2018Preceded byHema MaliniSucceeded byL. HanumanthaiahConstituencyKarnatakaPresidentBharatiya Janata Party, KarnatakaIn office2000–2003Preceded byB. S. YediyurappaSucceeded byAnanth KumarMember of ParliamentLok SabhaIn office1998–1999Preceded byQamar ul IslamSucceeded byIqbal Ahmed SaradgiConstituencyGulbargaMember of Karnataka Legislative CouncilIn office1 July 1990 –&#...

 

Not-for-profit credit union in California This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (April 2022) This article may contain excessive or irrelevant examples. Please help improve the article by adding descriptive text and removing less pertinent examples. (January 2021) Orange County's Credit UnionCompany typeCredit unionFounded1938Headquarters1701 E St Andrew Place 33°43′23″...

 

Kabinet Ekuador, nama resmi: Kabinet Revolusi Warga (Spanyol: Gabinete de la Revolución Ciudadanacode: es is deprecated ), adalah cabang eksekutif dari pemerintah Ekuador.[1] Kabinet diangkat oleh Presiden. Kabinet saat ini Pelantikan kabinet dilaksanakan pada tanggal 23 Mei 2017.[2] Kabinet Ekuador Masa Kepresidenan Lenín Moreno, 2017–sekarang Jabatan Nama Masa Jabatan Presiden Lenín Moreno 2017–sekarang Wakil Presiden María Alejandra Vicuña 2017–sekarang Menteri P...

Voce principale: Forlì Football Club. Associazione Calcio ForlìStagione 1964-1965Sport calcio Squadra Forlì Allenatore Libero Zattoni Presidente Giuseppe Goberti (Commissario Straordinario) Serie C18º posto nel girone B. Retrocesso in Serie D. Maggiori presenzeCampionato: Vittorio Spimi (34) Miglior marcatoreCampionato: Vittorio Spimi (6) StadioStadio Tullo Morgagni 1963-1964 1968-1969 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti l'Associa...

 

Warwickshire RingTwo boats entering lock 44 of the Hatton flight, the third from the topSpecificationsLength116 miles (187 km)Locks105StatusCanal ringNavigation authorityCanal & River Trust vteWarwickshire Ring Legend Fazeley Junction Coventry Canal Drayton Manor Theme Park Curdworth Locks (11) Tamworth Locks (2) M6 Toll motorway 57 yd Curdworth Tunnel Tamworth M42 motorway Minworth Locks (3) Birmingham and Fazeley Canal Salford JunctionNechells/Erdington Garrison Locks (5...

 

Barbadian cricketer Kraigg BrathwaiteBrathwaite batting during the first Test at Perth in December 2022Personal informationFull nameKraigg Clairmonte Brathwaite[1]Born (1992-12-01) 1 December 1992 (age 31)Bridgetown, BarbadosNicknameBoBoBattingRight-handedBowlingRight-arm off breakRoleOpening batterInternational information National sideWest Indies (2011–present)Test debut (cap 290)20 May 2011 v PakistanLast Test8 March 2023 v South AfricaODI d...

Cet article est une ébauche concernant une chanson lituanienne. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Discoteque Chanson de The Roop auConcours Eurovision de la chanson 2021 Sortie 2021 Langue Anglais Genre Électro-pop Classement 1re Demi-Finale : 4e (203 points) Finale : 8e (220 points) Chansons représentant la Lituanie au Concours Eurovision de la chanson On Fire(2020) Sentimentai(2...

 

Este artículo o sección tiene referencias, pero necesita más para complementar su verificabilidad. Busca fuentes: «Exposición Universal» – noticias · libros · académico · imágenesEste aviso fue puesto el 6 de marzo de 2018. Para otros usos de este término, véase Exposición (desambiguación). La Exposición Universal de París de 1900. Imagen coloreada a mano. Exposición Universal es el nombre genérico de varias exposiciones de gran envergadura celebradas ...

 

UFC mixed martial arts event in 2007 UFC 67: All or NothingThe poster for UFC 67: All or NothingInformationPromotionUltimate Fighting ChampionshipDateFebruary 3, 2007VenueMandalay Bay Events CenterCityLas Vegas, NevadaAttendance10,227 (8,700 paid)[1]Total gate$2,767,130[2]Buyrate350,000[3]Total purse$803,000 (disclosed)[4]Event chronology UFC Fight Night: Evans vs Salmon UFC 67: All or Nothing UFC 68: The Uprising UFC 67: All or Nothing was a mixed martial arts...

عمل تجاريمعلومات عامةصنف فرعي من منظمةكيان اقتصادي المالك رائد أعمال يدرسه إدارة أعمال له هدف ربح محاسبيالربح لديه جزء أو أجزاء مقاولةنشاط اقتصادي تصنيف للتصنيفات التي تحمل هذا الاسم تعديل - تعديل مصدري - تعديل ويكي بيانات جُزء من سلسلة مقالات حولالرأسمالية مفاهيم عمل تج�...

 

English squash player (born 1993) Declan JamesJames (left) against Borja Golán 2017Country EnglandResidenceNottingham, EnglandBorn (1993-04-19) 19 April 1993 (age 31)Nottingham, EnglandHeight6 ft 3 in (1.91 m)Weight83 kg (183 lb)Turned Pro2011RetiredActiveCoached byNick MatthewRacquet usedDunlop Hyperfibre+ Evolution 130Men's singlesHighest rankingNo. 15 (May 2019)Current rankingNo. 69 (May 2023)Title(s)13Tour final(s)21 Medal recor...

 

Nancy Kwan 關家蒨Kwan sekitar tahun 1960-anLahir19 Mei 1939 (umur 85)Hong KongTahun aktif1960–2010Suami/istriPeter Pock (m.1962)David Giler (m.1972)Norbert Meisel (1976–)AnakBernie Pock (1963-1996; almarhum)Orang tuaKwan Wing-hong dan Marquita ScottKerabatKa-keung Kwan - saudaraSitus webhttp://nancy-kwan.com/index.html Nancy Kwan Ka-shen (Hanzi tradisional: 關家蒨; Hanzi sederhana: 关家蒨; Pinyin: Guān Jiāqiàn; lahir 19 Mei 1939)[1] adalah seoran...

Effect pedal used manually with electric guitars to express a sweeping vocal quality This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Wah-wah pedal – news · newspapers · books · scholar · JSTOR (August 2020) (Learn how and when to remove this message) Thomas Organ Cry Baby (1970) manufactured by JEN Wah-wah p...

 

Loss of hair from the head or body Several terms redirect here. For other uses, Balding (surname), bald (disambiguation) and alopecia (disambiguation). Baldness redirects here. Not to be confused with boldness. Medical conditionHair lossOther namesAlopecia, baldnessA bald spot on a manPronunciationAlopecia: /ˌæləˈpiːʃ(i)ə, -si.ə/[1] SpecialtyDermatologySymptomsLoss of hair from part of the head or body.[2]ComplicationsPsychological distress[3]Types...

 

Chemical compound CamylofinClinical dataOther namesAcamylophenineAHFS/Drugs.comInternational Drug NamesATC codeA03AA03 (WHO) Identifiers IUPAC name Isopentyl 2-[2-(diethylamino)ethylamino]-2-phenylacetate CAS Number54-30-8 YPubChem CID5902ChemSpider5691 YUNII340B6Q764VChEMBLChEMBL253592 NCompTox Dashboard (EPA)DTXSID7046415 ECHA InfoCard100.000.184 Chemical and physical dataFormulaC19H32N2O2Molar mass320.477 g·mol−13D model (JSmol)Interactive image SMILES O=C(...

Untuk permainan video, lihat Halley's Comet (permainan video). 1P/Halley (Komet Halley)PenemuanDitemukan oleh:Prasejarah (observasi)Edmond Halley (Pengakuan periodisitas)Ditemukan tanggal:1758 (prediksi perihelion pertama)Karakteristik orbit AEpos:4 Agustus 2061 (2474040.5)Aphelion:35,2 SA(aphelion: 9 Desember 2023)[1]Perihelion:0,59278 SA[2]Sumbu semi-mayor:17,737 SAEksentrisitas orbit:0,96658Periode orbit:74,7 a[3]75thn 5m 19d perihelion ke perihelionInklinasi:161,96...

 

Women's downhill at the FIS Alpine World Ski Championships 2021LocationCortina d'Ampezzo, ItalyDate13 FebruaryCompetitors31 from 16 nationsWinning time1:34.27Medalists  Corinne Suter    Switzerland Kira Weidle   Germany Lara Gut-Behrami    Switzerland← 20192023 → FIS Alpine World Ski Championships 2021CombinedmenwomenDownhillmenwomenGiant slalommenwomenSlalommenwomenSuper-GmenwomenParallel g...

 

Зоны экваториального климата по Б. П. Алисову Экваториальный климат[1] — тип климата по классификации Б. П. Алисова, где господствует режим экваториальной депрессии, зоны пониженного атмосферного давления, обычно до 10° по обе стороны от экватора. Характеризуется слаб...

Aeropuerto Internacional Salgado Filho Aeroporto Internacional Salgado Filho IATA: POA OACI: SBPA FAA: LocalizaciónUbicación São João (Porto Alegre), BrasilElevación 3Sirve a Porto Alegre, BrasilDetalles del aeropuertoTipo PúblicoOperador FraportEstadísticas (2014)Operaciones aéreas 94.409Movimiento de pasajeros 8.447.307Movimiento de carga 20.886Pistas DirecciónLargoSuperficie11/293200AsfaltoMapa POA / SBPASitio web https://www.portoalegre-airport.com.br/ Fuentes: World Aero Data&#x...

 

Grand Prix Monako 1965 Lomba ke-2 dari 10 dalam Formula Satu musim 1965← Lomba sebelumnyaLomba berikutnya → Detail perlombaanTanggal 30 Mei 1965Nama resmi XXIII Grand Prix de MonacoLokasi Circuit de MonacoMonte CarloSirkuit Sirkuit jalan raya sementaraPanjang sirkuit 3.145 km (1.954 mi)Jarak tempuh 100 putaran, 314.500 km (195.421 mi)Posisi polePembalap Graham Hill BRMWaktu 1:32.5Putaran tercepatPembalap Graham Hill BRMWaktu 1:31.7 putaran ke-82PodiumPertama Graham Hil...