Курсовая работа: Аналіз методів рішення задачі лінійного програмування симплекс методом

Двоїстий симплекс метод, який приміняється до задачі в двоїстій базисній формі, приводить до послідовності задач із збільшуючим значаченням цільової функції з невідємними коефіцієнтами с _j ^’ , j =1, n і значеннями в_і , і=1,т будь-якого знаку. Двоїстий симплекс метод називають методом поступового покращення оцінок. Перебудова задачі виконується до тих пір, поки не буде встановлено, що вихідна задача не має допустимого рішення або буде отримана задача з допустимим базисним планом (всі в_і ≥0), який одночасно буде і оптимальним.

Розглянемо етапи рішення задач ЛП двоїстим симплекс методом:

1. Привести вихідну задачу до канонічного виду.

2. Виключити базисні змінні із цільової функції z .

3. Перевірити приведені коефіцієнти цільової функції: якщо всі преведені коефіцієнти с _j ^’ ≥0, j =1, n , а серед значень в_і , і=1,т, є від'ємні, то задача рішається двоїстим симплекс методом. Якщо серед приведених коефіцієнтів с _j ^’ є додатні, то в системі обмежень слід пребудувати вільні члени в невід'ємні (перемноживши на число (-1) стрічки, які містять від'ємні в_і ) і вирішувати задачу прямим симплекс методом.

4 . Опис логічної структури програми

Дана програма умовно розділена 8 модулів, які і утворюють програму, що розв′язує дану нам систему сиплекс методом. Всього є 8 модулів. Кожний модуль окремо відповідає за певну функцію, яку він повинен виконувати.

1. Модулі під назвою „colorPanel” та „numberCrunchingFrame”. Дані модулі відповідають за візуальне оформлення нашої програми. В ньому ми реалізовуєм кольори вікон,клавіші за допомогою яких ми будемо вводити данні і просуватися по програмі, розміри та всі інші параметри, які мають відношення до візульного оформлення нашої програми.

2. ”SimplexTool.java” В даному модулі ми ініціалізуємо основне вікно нашої програми. В ньому ми вводимо всі обмеження: кількість рівнянь в нашій системі (Constraint) та кількість обмежень (Variable).

3. Модуль „Matrix.java” даний модуль проводить всі дії з матрицями. Знаходить визначники, і т.д.

4. „Numbertextfield.java” Даний модуль перевіряє дані, які ввели з клавіатури на правильність. Тобто перевіряє правальність заданої кількості (в дані програмі можливо тільки від 2 до 7) рівнянь та обмежень функції.

5. „problemDimensionWindow.java” Даний модуль відповідає за діалогове вікно в яке ми вводимо початкові дані (коефіцієнти функції, рівнянь нашої системи рівнянь та знаки рівності або нерівності)

6. Модуль „revisedSimplex.java” реалізує сам симплекс метод. Наведемо деякі методи з даного класу:

а) publicrevisedSimplex(intnv, intnc) – ініціалізує об’єкти класу revisedSimplex: nv (NumberofVariables – кількість рівнянь), nc(NumberofConstrains – кількість обмежень)

б) public int iterateOneStep() – виконання поточної ітерації

в) publicintiterateOneStep()- відповідає за проведення усіх кроків одної ітерації.

г) publicfloatcalculateObjective() – функція знаходження значення цільової функції.

д) publicvoidchooseLeavingVariable() – знаходження змінної , яка буде виведена із базису.

е) publicvoidupdateSolution() – функція, яка обновляє рішення задачі

є) publicvoidChooseEnteringVariable() - знаходження змінної , яка буде введена в базис.

ж) publicbooleantestUnboundedness() – функція перевірки існування рішення.

з) publicvoidcalculateReducedCosts() – підрахунок значень індексної стрічки ()

(4.1)

и) publicbooleantestForOptimality() – перевірка, чи являється поточне значення цільової функції оптимумом, тобто вірним рцшенням.

і) privatevoidmakeBt() – заповнення матриці вільних членів

privatevoidmakeB() – заповнення основної матриці.

й) public void addConstraint(float [] coefficients, float rhs, int type) – додаванняумови

к) publicvoidspecifyObjective(float [] coefficients, booleantype) – відповідає за ініціалізацію цільової функції

л) publicbooleanpreprocess(intnumberOfVariables, intnumberOfConstraints) – функція, заповнення и виведення данних, які ми вводимо на екран.