عنوان

الگوريتم هاي جواب براي مسئله مقدار بهينه معکوس روي درخت هاي فراگيرحداقل

Number

۴۹۳۴پ

.Language of Text, Soundtrack etc

فارسی

Title Proper

الگوريتم هاي جواب براي مسئله مقدار بهينه معکوس روي درخت هاي فراگيرحداقل

General Material Designation

[پایان نامه]

First Statement of Responsibility

سیرانزاده، روح‌الله

Name of Publisher, Distributor, etc.

صنعتی سهند

Date of Publication, Distribution, etc.

۱۴۰۱

Specific Material Designation and Extent of Item

۱۰۷ص.

Other Physical Details

مصور، جدول، نمودار

Accompanying Material

CD

Dissertation or thesis details and type of degree

کارشناسی ارشد

Discipline of degree

ریاضی کاربردی- بهینه‌سازی

Date of degree

۱۴۰۱/۱۱/۰۱

Text of Note

در این پایان نامه، ابتدا مسئله مقدار بهینه معکوس روی درخت فراگیر مینیمم تحت نرم بی نهایت مورد بررسی قرار می گیرد. هدف این مسئله تغییر دادن وزن یالهای گراف غیر جهتدار هم بند G=(V,E,w) و درخت فراگیر T^0 است بطوریکه T^0 تحت بردار وزن یالی جدید درخت فراگیر مینیمم باشد و مجموع وزن یالهای T^0 برابر مقدار از پیش تعیین شده K باشد و هم چنین هزینه تغییرات وزن یالها تحت نرم بی نهایت به حداقل برسد. نشان داده می‌شود که مسئله تحت نرم بی نهایت به‌صورت یک مدل برنامه‌ریزی غیر خطی فرمول‌بندی ‌می شود، برخی ویژگیهای جواب شدنی و جواب بهینه مسئله مورد تحلیل قرار می گیرد. هم چنین یک شرط لازم و کافی برای جواب بهینه مسئله بیان و اثبات می شود. در ادامه یک الگوریتم با زمان اجرای چندجمله ای قوی O(|V||E|) پیشنهاد می شود و یک مثال عددی برای نشان دادن کارایی الگوریتم ارائه می گردد.در قسمت پایانی، به مسئله مقدار بهینه معکوس با کران پایین L روی درخت فراگیر مینیمم تحت نرم بی نهایت پرداخته می شود. هدف این مسئله، پیدا کردن یک بردار وزن یالی جدید با کران پایین L است بطوریکه T^0 تحت این بردار وزن جدید یک درخت فراگیر مینیمم با وزن K باشد و تابع هدف، هزینه تغییرات را تحت نرم بی نهایت مینیمم کند. پس از بیان مدل ریاضی مسئله و برخی ویژگیهای جواب شدنی و جواب بهینه مسئله، سه الگوریتم با زمان اجرای O(|E|) برای پیدا کردن جواب شدنی مسئله ویک الگوریتم با زمان اجرای O(|V||E|) برای پیدا کردن جواب بهینه مسئله پیشنهاد می شود و در نهایت با حل یک مثال عددی کارایی الگوریتم ها نشان داده می شود.

Text of Note

In this thesis, first, the inverse optimal value problem on minimum spanning tree underunit l∞ norm is investigated. The purpose of this problem is to modify the weight of theedges of the undirected connected graph G = (V, E, w) and the spanning tree T0such thatT0 under the new edge weight vector of the spanning tree is minimum and the sum of theweights of the edges of T0should be equal to the given value of K and the modification costunder l∞ norm is minimized. It is shown that the problem under l∞ norm is formulated as anon-linear programming model. Some properties of the optimal solution of the problem areanalyzed. Also, a necessary and sufficient condition for the optimal solution of the problemis stated and proved. In the following, an algorithm with a strong polynomial running timeO(|V ||E|) and a numerical example is proposed to prove the efficiency of the algorithm.In the final part, the lower bounded inverse optimal value problem on minimum spanningtree under l∞ norm is addressed. The goal of this problem is to find a new weight vector withlower bound L such that T0 under this new weight vector is a minimum spanning tree withweight K and the objective function is to minimize the modification cost under l∞ norm.After stating the mathematical model of the problem and some solvable properties and theoptimal solution of the problem, three algorithms with an running time of O(|E|) to find afeasible solution of the problem and an algorithm with the running time of O(|V ||E|) areproposed to find the optimal solution of the problem. finally, the efficiency of the algorithmsis shown by solving a numerical example

Variant Title

Solution Algorithms for the Inverse Optimal Value Problem on Minimum Spanning Trees

درخت فراگیر مینیمم

نرم بی نهایت

مسئله مقدار بهینه معکوس

الگوریتم چند جمله ای قوی

Subject Term

درخت فراگیر مینیمم، نرم بی نهایت ، مسئله مقدار بهینه معکوس،الگوریتم چند جمله ای قوی

Subject Term

Minimum spanning tree, l∞ norm, Inverse optimal value problem, Strongly polynomial time algorithm

سیرانزاده، روح‌الله

Entry Element

باروقی

Entry Element

علیزاده

Part of Name Other than Entry Element

، فهیمه

Part of Name Other than Entry Element

، بهروز

Relator Code

استاد راهنما

Relator Code

استاد راهنما

Entry Element

صنعتی سهند

Country

ایران

Agency

دانشگاه صنعتی سهند

Call Number

ریاضی، ۴۰۲۹۱، ۱۴۰۱

p

TF

92029

a

Y