### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Linear Programming CSCI 628

GPA 3.56

### View Full Document

## 20

## 0

## Popular in Course

## Popular in ComputerScienence

This 11 page Class Notes was uploaded by Aliza Ruecker on Thursday October 29, 2015. The Class Notes belongs to CSCI 628 at College of William and Mary taught by David Phillips in Fall. Since its upload, it has received 20 views. For similar materials see /class/231164/csci-628-college-of-william-and-mary in ComputerScienence at College of William and Mary.

## Reviews for Linear Programming

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

Produced with a Trial Version of PDF Annotator wwwPDFAnnotatorcom An example of the simplex algorithm Original LP maximize 3r1 332 2 1 subjectto xi m 3m s 30 a 5ar 5 2 2r1 2m m g 24 J 95 3 4r1 2 2 g 36 w HJ chnw 4 I1ir2ira 2 UV 9395 N 5 Canoich Exam Standard form r J 3 quot a F uLVI3 Ua l ykts B l39G S ivesquot iM uni Kan Iliad IH quot X6 m43 X 5 4 QS SVVV lt10 H 5 B 39 i 39 39 8 11 lt12 lt13 H H p m 53 N H m H r Q 8 Produced with a Trial Version of PDF Annotator wwwPDFAnnotatorcom WK 3 L 439 2x3 K x 4v 3yJ WV 30 2quot 7quotL X3 mgr 7 gtlt39xL I39Zx La3c Y o MAJu A Basis 5 3 I IZLS To 9 m Px gum ggf 5th 0 Mo SOLQ for x KL XV H h t39 SHcsu y XL W 3 0 2x Flyl Llyl XL 3 a podium 4 u 50uh uvg Acons 45k 56 39 unhqu sohkw 39 l nquot nquotVk3 Ran L coe icld who lt QSSUM an it Tl CDQ W 0 F5 Pu N vv39rmk39f 41 our COWSHQ39kH x m Q Ma rx q39ll qI1 Alix A 02 l we W a a n a Wquot Lt 1min rIKO ePwanyf Producelvgitia Trial Velzlslior f PDF rlrlotal WAnnotatorcom sake M 6 51 are 1 thA 452 qu i 5w 4U 44L14ke1 we a 5 w 0 IV 5 w ka 4quot 0 Mn less 1 dk O lumih m39 39 9 o o Cm z lkd my a UL a V 3 f a o a 3 a MM 4 as ahaM We WW5 IMLO5 m ebluws 5 A W am I m EAJC WW3 Ts our w Mk uwwt wo 71mm 4Wquot 123 Umlogm MA MT A mg wLo7 nab40 Ml no Mk w39 aSSM hon s a A 141 1 I n 4 A JIALM r 1na0n nq 7 M4 Cous h6v is reOQhKM Prgyc prl f Trial Ve 39on PDF rmo atok vww FAnnotatorcom 0 hayH39c LP Ska th r Z 0quot 1M an KRha L a I 5 3 Um quot 9 KNR an gnaw 3 vanLl F 5 SnJl km 1 umhhg quot urJa L Ha A c f39oknw 29d ch go b H w Baum QHMJ th 5 Bun 59c sz solw wv8FSo lmzc was o is hinncvupwc Sufrese UL Ma1 Win 0 fan q3 K x P3 3quot H 30 hs ZX39 F 7 7 S 3 H L LL Sobi 75 x xL P2X 323 t I a 0 r AWXuLc drhdwe Mo s Seh t gt P 00quot 509 1 0139 buys a axJedhivg VWL 9 O quot lt QIKLA3 o Mun ms 5 a Shh BPS c sc conclude b f1 35 LP IRF usuk x mmgrmm Ewg wgm mas om c go o UUHgt087003 no 81K Lv Very 25 w 2L 0 5511 rlmu 05 v u rn N 055 Av mar 5 ftH Fa 04X 111 Capo in 3111 01gt Esrawcc xv 55750 huv 1 we 13 rr Eran mplb fr PAch nitrer I crasxnnef TX 124537 I AWV hF 9 Tu 00 03 Nag Qafxxck uLFItAI m3 3 Po Tarts 319 le 53 T PIT nets mix TPFHW Lars P1 PJifJF roarJ Produced with a Trial Version of PDF Annotator wwwPDFAnnotatorcom A Degenerate LP De nition An LP is degenerate if in a basic feasible solution one of the basic variables takes on a zero value Degeneracy is a problem in practice because it makes the simplex algorithm slower Original LP maximize 51 52 53 1 subject to 321 02 g 8 7 x 4 1739 rs 3 2 7 lt 52 53 i 0 47 XL 4x 4 3L Q 3 33175527 2 0 4 Standard form A U V Z 15 2CE3 A Ch V 81 8 7 551 7 552 82 O 7 552 553 a Jayeverach A 1 V Produced with a Trial Version of PDF Annotator wwwPDFAnnotatorcom Iteration 1 z 8 81 8 82 A kar F Note that one of the basic variables is 0 We choose 51 as the entering variable and 51 as the leaving variable N H 00 H m l H m l 3 H AAA gt ngt ngt n WMH VVV Note again that one of the basic variables is 0 The previous pivot did increase the objective function value from 0 to 8 though 995 quot k Bed 5 OM rqmdole WV M Produced with a Trial Version of PDF Annotator wwwPDFAnnotatorcom Iteration 2 z 8 03 51 P s 14 551 8 7 552 81 B Z X L39s 82 552 7 553 We now choose 53 as the entering variable and 52 as the leaving variable These were our only choices A H 1 3 3939738 AA DOD Note that the objective function did not increase This occurs because of degeneracy Iteration 3 Z 8 132 81 82 131 8 132 81 333 i 332 52 22 Z 171 251 52 132 8 131 81 133 8 131 81 82 Since all coef cients of variables in the objective function are negative we now have the optimal solution 1235152 O8800 with objective value 16 Notice that in the nal solution the basic variables are all non zero In a degenerate LP it is also possible that even in the nal solution some of the basic variables will be zero One other thing to note is that 51 was an entering variable in one iteration and a leaving variable in another In general a variable can be an entering and leave the basic many times in the course of the simplex algorithm Produced with a Trial Version of PDF Annotator wwwPDFAnnotatorcom CSCI 628 7 Introduction to Linear Programming Cycling maxz Ezl 715012 13 7614 at 11 76012 7 914 15 0 zl 79012 7 314 15 0 1 13 17 1 17 27 37 47 57 167 x7 2 0 6 st We n 39 Q 0Q6OZZ 2175 7914 Ac z x 0 5 0 711 90 5170 7314 L 2 Z7 1 713 z 0 15012 5170 7614 y xi 0 24OZZ 2475 73614 7415 8 03 o 7 1514 215 ac 1 7903 XL 02 z 0 3012 510 73314 7315 xi 7 84 1215 7815 2 414 Jr zs 317316 4 Z7 W5 Produced with a Trial Version of PDF Annotator wwwPDFAnnotatorcom g r 13 0 711 Jr 12 0 n 11 1 7 1 zl 715 z 0 i 215 13 7 0 zl Z4 0 in Z7 1 711 z 0 zl Z5 0 in 721012 Z4 0 711 3012 Z7 1 z 0 zl 733012 I M SWMM a a Stlc 7 6022 2175 1 1 EZI 9012 EZB 7953 715012 5170 72515 zs 2515 7315 7914 7614 K14

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.