<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom" xmlns:dc="http://purl.org/dc/elements/1.1/">
  <channel>
    <title>DEV Community: derek singh</title>
    <description>The latest articles on DEV Community by derek singh (@drs0429).</description>
    <link>https://dev.to/drs0429</link>
    <image>
      <url>https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F4255805%2F7a23c4e3-f8d5-4f31-9692-a99352dd9051.png</url>
      <title>DEV Community: derek singh</title>
      <link>https://dev.to/drs0429</link>
    </image>
    <atom:link rel="self" type="application/rss+xml" href="https://dev.to/feed/drs0429"/>
    <language>en</language>
    <item>
      <title>How to know your linear program's answer is really the best (a product-mix example in Python)</title>
      <dc:creator>derek singh</dc:creator>
      <pubDate>Fri, 20 Nov 2026 13:43:18 +0000</pubDate>
      <link>https://dev.to/drs0429/how-to-know-your-linear-programs-answer-is-really-the-best-a-product-mix-example-in-python-4mna</link>
      <guid>https://dev.to/drs0429/how-to-know-your-linear-programs-answer-is-really-the-best-a-product-mix-example-in-python-4mna</guid>
      <description>&lt;p&gt;A solver says "optimal". How do you know it is right, and that no better plan exists? For a linear program there is a short, checkable proof: the &lt;strong&gt;dual&lt;/strong&gt;. Here it is on the smallest useful example.&lt;/p&gt;

&lt;h2&gt;
  
  
  The problem
&lt;/h2&gt;

&lt;p&gt;A company makes two products, A and B.&lt;/p&gt;

&lt;div class="table-wrapper-paragraph"&gt;&lt;table&gt;
&lt;thead&gt;
&lt;tr&gt;
&lt;th&gt;&lt;/th&gt;
&lt;th&gt;Labour (hours)&lt;/th&gt;
&lt;th&gt;Raw material (units)&lt;/th&gt;
&lt;th&gt;Profit ($)&lt;/th&gt;
&lt;/tr&gt;
&lt;/thead&gt;
&lt;tbody&gt;
&lt;tr&gt;
&lt;td&gt;One A&lt;/td&gt;
&lt;td&gt;2&lt;/td&gt;
&lt;td&gt;1&lt;/td&gt;
&lt;td&gt;3&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;One B&lt;/td&gt;
&lt;td&gt;1&lt;/td&gt;
&lt;td&gt;2&lt;/td&gt;
&lt;td&gt;2&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Available&lt;/td&gt;
&lt;td&gt;100&lt;/td&gt;
&lt;td&gt;80&lt;/td&gt;
&lt;td&gt;&lt;/td&gt;
&lt;/tr&gt;
&lt;/tbody&gt;
&lt;/table&gt;&lt;/div&gt;

&lt;p&gt;How many of each should it make to earn the most profit?&lt;/p&gt;

&lt;h2&gt;
  
  
  Step 1: the model in words, then in math
&lt;/h2&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Decisions:&lt;/strong&gt; &lt;code&gt;a&lt;/code&gt; = units of A made, &lt;code&gt;b&lt;/code&gt; = units of B made (both 0 or more).&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Objective:&lt;/strong&gt; total profit, &lt;code&gt;3a + 2b&lt;/code&gt; dollars, as large as possible.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Rules:&lt;/strong&gt; labour used, &lt;code&gt;2a + b&lt;/code&gt;, is at most 100 hours; material used, &lt;code&gt;a + 2b&lt;/code&gt;, is at most 80 units.
&lt;/li&gt;
&lt;/ul&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight minizinc"&gt;&lt;code&gt;&lt;span class="n"&gt;maximize&lt;/span&gt;    &lt;span class="mi"&gt;3a&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mi"&gt;2b&lt;/span&gt;          # &lt;span class="n"&gt;profit&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;$&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="n"&gt;subject&lt;/span&gt; &lt;span class="k"&gt;to&lt;/span&gt;  &lt;span class="mi"&gt;2a&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt;  &lt;span class="n"&gt;b&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;=&lt;/span&gt; &lt;span class="mi"&gt;100&lt;/span&gt;   # &lt;span class="n"&gt;labour&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;hours&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
             &lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mi"&gt;2b&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;=&lt;/span&gt; &lt;span class="mi"&gt;80&lt;/span&gt;    # &lt;span class="n"&gt;raw&lt;/span&gt; &lt;span class="n"&gt;material&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;units&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
             &lt;span class="n"&gt;a&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt; &lt;span class="o"&gt;&amp;gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;       # &lt;span class="n"&gt;cannot&lt;/span&gt; &lt;span class="n"&gt;make&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="n"&gt;negative&lt;/span&gt; &lt;span class="n"&gt;amount&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Everything is linear, so this is a &lt;strong&gt;linear program (LP)&lt;/strong&gt;: the best answer is at a corner of the region the rules allow, and a solver can find it and prove it.&lt;/p&gt;

&lt;h2&gt;
  
  
  Step 2: solve it with cvxpy
&lt;/h2&gt;



&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight python"&gt;&lt;code&gt;&lt;span class="k"&gt;import&lt;/span&gt; &lt;span class="n"&gt;cvxpy&lt;/span&gt; &lt;span class="k"&gt;as&lt;/span&gt; &lt;span class="n"&gt;cp&lt;/span&gt;

&lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;cp&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Variable&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;nonneg&lt;/span&gt;&lt;span class="o"&gt;=&lt;/span&gt;&lt;span class="kc"&gt;True&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;   &lt;span class="c1"&gt;# units of product A&lt;/span&gt;
&lt;span class="n"&gt;b&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;cp&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Variable&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;nonneg&lt;/span&gt;&lt;span class="o"&gt;=&lt;/span&gt;&lt;span class="kc"&gt;True&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;   &lt;span class="c1"&gt;# units of product B&lt;/span&gt;
&lt;span class="n"&gt;labour&lt;/span&gt;   &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="o"&gt;*&lt;/span&gt;&lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="o"&gt;*&lt;/span&gt;&lt;span class="n"&gt;b&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;=&lt;/span&gt; &lt;span class="mi"&gt;100&lt;/span&gt;    &lt;span class="c1"&gt;# hours of labour&lt;/span&gt;
&lt;span class="n"&gt;material&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="o"&gt;*&lt;/span&gt;&lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="o"&gt;*&lt;/span&gt;&lt;span class="n"&gt;b&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;=&lt;/span&gt; &lt;span class="mi"&gt;80&lt;/span&gt;     &lt;span class="c1"&gt;# units of raw material&lt;/span&gt;
&lt;span class="n"&gt;prob&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;cp&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Problem&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;cp&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Maximize&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;3&lt;/span&gt;&lt;span class="o"&gt;*&lt;/span&gt;&lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="o"&gt;*&lt;/span&gt;&lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;labour&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;material&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="n"&gt;prob&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nf"&gt;solve&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;solver&lt;/span&gt;&lt;span class="o"&gt;=&lt;/span&gt;&lt;span class="n"&gt;cp&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;HIGHS&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;

&lt;span class="k"&gt;print&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;prob&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="n"&gt;status&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;prob&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="n"&gt;value&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="n"&gt;value&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="n"&gt;value&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="k"&gt;print&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;labour&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="n"&gt;dual_value&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;material&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="n"&gt;dual_value&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Output (cvxpy 1.9.3, HiGHS):&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;optimal 160.0 40.0 20.0
1.333333 0.333333
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;So: &lt;strong&gt;make 40 units of A and 20 units of B, for a profit of $160.&lt;/strong&gt; Both rules are used to the limit: labour 2(40) + 20 = 100 hours, material 40 + 2(20) = 80 units.&lt;/p&gt;

&lt;h2&gt;
  
  
  Step 3: check it is feasible
&lt;/h2&gt;

&lt;p&gt;Plug the answer back into every rule: 100 ≤ 100 hours ✓, 80 ≤ 80 units ✓, 40 ≥ 0 and 20 ≥ 0 ✓. Feasible means "allowed", not yet "best".&lt;/p&gt;

&lt;h2&gt;
  
  
  Step 4: prove it is the best, with the dual
&lt;/h2&gt;

&lt;p&gt;The two numbers on the second line are the &lt;strong&gt;dual values&lt;/strong&gt; (also called shadow prices):&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;one more labour hour is worth &lt;strong&gt;$4/3 ≈ $1.33&lt;/strong&gt; of extra profit;&lt;/li&gt;
&lt;li&gt;one more unit of raw material is worth &lt;strong&gt;$1/3 ≈ $0.33&lt;/strong&gt;.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;They give a proof in two lines:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;
&lt;strong&gt;They price every product at least at its profit.&lt;/strong&gt; Product A uses 2 hours and 1 unit: 2(4/3) + 1(1/3) = 3 ≥ $3 ✓. Product B uses 1 hour and 2 units: 1(4/3) + 2(1/3) = 2 ≥ $2 ✓. So any plan's profit is at most the value of the resources it uses.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;So no plan can beat the value of all the resources:&lt;/strong&gt; 100 hours × $4/3 + 80 units × $1/3 = &lt;strong&gt;$160&lt;/strong&gt;.&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;Every feasible plan earns at most $160, and ours earns exactly $160. That is optimal, with no trust in the solver required: anyone can redo the arithmetic. This is &lt;strong&gt;weak duality&lt;/strong&gt; (dual value ≥ any profit) closing with &lt;strong&gt;strong duality&lt;/strong&gt; (they meet, gap 0).&lt;/p&gt;

&lt;p&gt;You can check it by hand too: the corners of the allowed region are (0, 0) → $0, (50, 0) → $150, (0, 40) → $80 and (40, 20) → $160.&lt;/p&gt;

&lt;h2&gt;
  
  
  What the dual tells a manager
&lt;/h2&gt;

&lt;p&gt;The shadow prices are useful on their own: if someone offers an extra labour hour for less than $1.33, take it; raw material is worth only $0.33 a unit at the margin. (These values hold for small changes, until another rule starts to bind.)&lt;/p&gt;

&lt;h2&gt;
  
  
  The takeaway
&lt;/h2&gt;

&lt;p&gt;For any LP, ask for three things, not one: the &lt;strong&gt;status&lt;/strong&gt; (optimal, infeasible, unbounded), &lt;strong&gt;feasibility&lt;/strong&gt; of every rule, and a &lt;strong&gt;dual certificate&lt;/strong&gt; whose value matches the objective. If the gap is 0, the answer is proven.&lt;/p&gt;




&lt;p&gt;&lt;em&gt;This article was written with AI assistance; every number in it comes from the solver run shown above and was checked by hand.&lt;/em&gt;&lt;/p&gt;

&lt;p&gt;I build ProvenDecisions, a web app that does these steps for you, from typed math, LaTeX, a photo or a spoken problem, and shows the dual check with every answer. This example is solved there: &lt;a href="https://proven-decisions.ai/examples/product-mix?ref=devto" rel="noopener noreferrer"&gt;https://proven-decisions.ai/examples/product-mix?ref=devto&lt;/a&gt;&lt;/p&gt;

</description>
      <category>optimization</category>
      <category>python</category>
      <category>math</category>
      <category>tutorial</category>
    </item>
  </channel>
</rss>
