Parametrik Program 0-1 Integer Campuran

Abstract

Two algorithms that are suggested for general case MILP . MILP parametric where one parameter can affect the goal function altogether, the right-hand-side, and matrix. The first algorithm is based on branch and bound algorithm at integer variable, to solve parametric linear programming at every node. Second algorithm is based on invariant solution qualitative optimality, pointing parametric optimization problems to be a bunch of MILP regular, parametric, linear program and MINLP. Number of sub problems required for a particular instance is equal to the number of critical areas. Improvement of the well-known simplex algorithm rationally presented, which requires less operating successively on rational functions.

Dua algoritma untuk kasus umum parametrik Mixed Integer Linear Programming ( MILP ) yang diusulkan. Parametrik MILP di mana satu parameter secara bersamaan dapat mempengaruhi fungsi tujuan, sisi kanan dan matriks. Algoritma pertama didasarkan pada perluasan algoritma Branch and Bound (BnB) pada variabel integer, memecahkan parametrik program linear (LP) di setiap node. Algoritma kedua didasarkan pada kisaran optimalitas solusi kualitatif yang invarian, merujuk masalah optimisasi parametrik menjadi serangkaian MILPs reguler, parametrik LP dan algoritma Mixed Integer Non-Linear Programming (MINLP). Jumlah submasalah yang diperlukan untuk contoh tertentu adalah sama dengan jumlah daerah kritis. Perbaikan dari algoritma simpleks yang terkenal rasional disajikan, yang memerlukan operasi yang lebih sedikit berturut-turut pada fungsi rasional.