در این آموزش ویدیویی، نحوه پیاده سازی الگوریتم لاگرانژ (ساب گرادیانت) برای مسئله کشاورز با استفاده از گمز ارائه شده است. ویدیو آموزشی نیز در انتهای مطلب قرار دارد که می توانید از یوتیوب نیز آن را تماشا نمایید.
مدل مسئله کشاورز در حالت غیر قطعی (تصمیمات دو مرحله ای) به صورت زیر می باشد :
زیر مسئله لاگرانژ برای مسئله کشاورز
محدودیت (۱) را آزاد کرده و با ضریب λ به تابع هدف منتقل می کنیم:
در ادامه با استفاده از روش زیر گرادیان مسئله لاگرانژ را حل می نماییم.
مراحل روش زیر گرادیان
فرض کنید k شمارنده ی تکرار، LB بهترین کران پایین که تاکنون پیدا شده، UB یک کران بالا روی تابع هدف مسئله دوگان لاگرانژ، k1 تعداد تکرارهای متوالی که بهبودی در مقدار کران پایین ایجاد نشده و K1 یک حد بالا روی مقدار k1 باشد، همچنین فرض کنید τ کنترل کننده ی اندازه گام، λ ضریب لاگرانژ در تکرار k ام و K یک حد بالا روی تعداد تکرارها باشد.
مرحله ی اول : مقداردهی اولیه
K1 را برابر با ۴ در نظر میگیریم، یعنی اگر بعد از ۴ تکرار متوالی بهبودی در کران پایین ایجاد نشد، τ را نصف می کنیم و قرار می دهیم :
همچنین قرار میدهیم UB=-53100 که متناظر با جواب شدنی زیر مسئله برای مسئله کشاورز است.
مرحله دوم : حل زیر مسئله لاگرانژ
برای تعیین بردار زیر گرادیان ωk در λk، زیرمسئله لاگرانژ را به ازای λ=λk حل می کنیم با فرض اینکه x2، x1 و x3 جواب بهین آن باشد، قرار می دهیم:
آن گاه قرار می دهیم k1=0 وLB=zLR(λk)، در غیر اینصورت، قرار می دهیم k1=k1+1، اگر مقدار k1=K1 باشد، مقدار τ را نصف کرده و قرار می دهیم k1=0.
مرحله سوم : بررسی بهینگی
اگر ۰≥ωk و ωk(λk) باشد، شرط مکمل کمکی برقرار است و xk یک جواب بهین برای مسئله اولیه است و λk یک جواب بهین برای مسئله دوگان لاگرانژ است. پس روند را متوقف می کنیم، در غیر اینصورت به مرحله چهارم می رویم.
مرحله چهارم : بروزرسانی ضرایب لاگرانژ
اگر k=K، متوقف می شویم، در غیر اینصورت قرار می دهیم:
سپس قرار می دهیم k=k+1 و به مرحله دوم باز می گردیم.
