ວິທີການ Simplex ແລະຄໍາຮ້ອງສະຫມັກຂອງມັນ

ທຸກໆການແກ້ໄຂຮູບພາບຂອງບັນຫາທີ່ເກີດຂື້ນໃນ ການຂຽນໂປລແກລມຕາມເສັ້ນທາງ ກໍານົດວ່າການແກ້ໄຂທີ່ດີທີ່ສຸດຂອງບັນຫາໃດໆແມ່ນກ່ຽວຂ້ອງຢ່າງເຕັມສ່ວນກັບຈຸດທີ່ສຸດຂອງຊຸດ (ຫຼືຈຸດແຈຂອງຊ່ອງ). ຄວາມຄິດນີ້ແມ່ນອີງໃສ່ວິທີການງ່າຍດາຍໂດຍທົ່ວໄປຂອງຄະນິດສາດເພື່ອແກ້ໄຂບັນຫາທີ່ອະນຸຍາດໃຫ້ແກ້ໄຂບັນຫາການຂຽນໂປຼແກຼມໃດໆ.

ເພື່ອຍ້າຍຈາກວິທີເລຂາຄະນິດຂອງການແກ້ໄຂບັນຫາກັບການແກ້ໄຂໂດຍນໍາໃຊ້ວິທີການງ່າຍດາຍຂອງການຂຽນໂປລແກລມແບບເລັ່ງ, ມັນຈໍາເປັນຕ້ອງໄດ້ອະທິບາຍຈຸດທີ່ສຸດທີ່ສຸດຂອງຊ່ອງໂດຍນໍາໃຊ້ວິທີການສະກົດຖານ. ເພື່ອປະຕິບັດການປ່ຽນແປງນີ້, ທ່ານຈໍາເປັນຕ້ອງນໍາພາວຽກງານການຂຽນໃດໆເຂົ້າໄປໃນແບບຟອມມາດຕະຖານ (ຍັງເອີ້ນວ່າ Canonical).

ເພື່ອເຮັດສິ່ງນີ້, ທ່ານຈໍາເປັນຕ້ອງປະຕິບັດຕາມຂັ້ນຕອນຕໍ່ໄປນີ້:

• ຫັນປ່ຽນຄວາມບໍ່ສະເຫມີພາບຂອງບັນດາຂໍ້ຈໍາກັດໃນຄວາມສະເຫມີພາບ (ໄດ້ຮັບຮູ້ໂດຍນໍາສະເຫນີຕົວແປໃຫມ່);
• ບັນຫາການ maximization ຕ້ອງໄດ້ຮັບການປ່ຽນແປງເປັນບັນຫາຫຼຸດຜ່ອນ;
• ມັນເປັນສິ່ງຈໍາເປັນທີ່ຈະໄດ້ຮັບຕົວແປທີ່ບໍ່ແມ່ນທາງລົບ, ການປ່ຽນແປງຕົວແປຟຣີທັງຫມົດເຂົ້າໄປໃນພວກມັນ.

ຮູບແບບຂອງບັນຫາແບບຟອມມາດຕະຖານທີ່ໄດ້ຮັບມາເປັນຜົນມາຈາກການປ່ຽນແປງທັງຫມົດຈະຊ່ວຍໃຫ້ພວກເຮົາສາມາດຕັດສິນໃຈແກ້ໄຂພື້ນຖານໄດ້. ຊຶ່ງ, ໃນທີ່ສຸດ, ກໍານົດຢ່າງຈະແຈ້ງຈຸດທັງຫມົດທີ່ແຈຂອງຊ່ອງ. ຫຼັງຈາກນັ້ນ, ວິທີການງ່າຍດາຍຈະຊ່ວຍໃຫ້ພວກເຮົາຊອກຫາວິທີແກ້ໄຂທີ່ດີທີ່ສຸດຈາກທັງຫມົດພື້ນຖານທີ່ໄດ້ຮັບ.

ສິ່ງທີ່ສໍາຄັນທີ່ເຮັດໃຫ້ວິທີການແກ້ໄຂບັນດາວຽກງານທີ່ມີເງີນໃນການປະຕິບັດນັ້ນແມ່ນການປັບປຸງທີ່ສອດຄ່ອງແລະຄົງທີ່ໃນການປະຕິບັດແຜນການເຊິ່ງຜົນໄດ້ຮັບແມ່ນການປະຕິບັດວຽກທີ່ມີປະສິດທິພາບສູງສຸດ. ສິ່ງທີ່ສໍາຄັນທີ່ທ່ານຕ້ອງເຮັດເພື່ອໃຫ້ໄດ້ຜົນທີ່ຕ້ອງການຄືການປະຕິບັດມັນຢ່າງຖືກຕ້ອງໃນແບບຟອມຄະນິດສາດແລະໂຄງການ.

ຜົນຂອງການພັດທະນາທັງຫມົດຄວນເປັນວິທີງ່າຍໆ, ເຊິ່ງເປັນຂັ້ນຕອນການຄິດໄລ່ພິເສດໂດຍອີງໃສ່ການປັບປຸງຢ່າງຕໍ່ເນື່ອງຂອງການແກ້ໄຂຕໍ່ໆໄປ. ນີ້ເກີດຂື້ນໂດຍການປຽບທຽບຄູ່ຈຸດທັງຫມົດຂອງຍົນແລະຊອກຫາທີ່ດີທີ່ສຸດ.

ມັນໄດ້ຖືກພິສູດໃຫ້ເຫັນວ່າການຄົ້ນຫາທັງຫມົດສໍາລັບການແກ້ໄຂທີ່ດີທີ່ສຸດ (ໃນກໍລະນີຖ້າມີ) ແມ່ນສໍາເລັດສໍາລັບທັງຫມົດແລະຈໍານວນຂັ້ນຕອນທີ່ຈໍາກັດ. ການຍົກເວັ້ນພຽງແຕ່ວ່າວິທີການງ່າຍດາຍບໍ່ສາມາດຈັດການແມ່ນ "ບັນຫາທີ່ເສື່ອມເສີຍ". ໃນກໍລະນີນີ້, ມີອັນທີ່ເອີ້ນວ່າ "looping", ຊຶ່ງເຮັດໃຫ້ການຄ້າງຫ້ອງຄົງທີ່ຂອງວຽກງານດຽວກັນເປັນຈໍານວນເວລາທີ່ບໍ່ຈໍາກັດ.

ວິທີການງ່າຍດາຍໄດ້ພັດທະນາກັບຄືນມາໃນປີ 1947. "ພໍ່ແມ່" ຂອງລາວແມ່ນນັກຄະນິດສາດຈາກສະຫະລັດ George Danzig. ໃນທັດສະນະຂອງຄວາມຈິງທີ່ວ່າວິທີງ່າຍໆມີແບບປະຫວັດສາດຍາວນານ, ມັນເປັນຫນຶ່ງໃນຫຼາຍທີ່ສຸດທີ່ໄດ້ສຶກສາແລະປະສິດທິພາບຫຼາຍທີ່ສຸດສໍາລັບການຊອກຫາວິທີແກ້ໄຂທີ່ດີທີ່ສຸດຕໍ່ບັນຫາໃດຫນຶ່ງທີ່ປະເຊີນກັບບຸກຄົນໃດຫນຶ່ງ.

ວິທີການເພີ່ມປະສິດທິພາບຂັ້ນຕອນໂດຍຂັ້ນຕອນຫຼາຍຢ່າງງ່າຍດາຍກິດຈະກໍາໃດໆຂອງສັງຄົມ. ມັນສາມາດຖືກນໍາໃຊ້ໃນດ້ານວິທະຍາສາດແລະຜະລິດຕະພັນທັງຫມົດ. ຄໍາຮ້ອງສະຫມັກຢ່າງກວ້າງຂວາງຂອງມັນຈະຊ່ວຍໃຫ້ວິທີການແກ້ໄຂບັນຫາທີ່ຖືກຕ້ອງເພື່ອບັນຫາທີ່ສະລັບສັບຊ້ອນ.