50278 (Аналіз методів рішення задачі лінійного програмування симплекс методом), страница 2

2016-07-30СтудИзба

Описание файла

Документ из архива "Аналіз методів рішення задачі лінійного програмування симплекс методом", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "50278"

Текст 2 страницы из документа "50278"

3.2 Симплекс-метод

Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.

Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.

Розглянемо опис методу:

Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:

(3.2.1)

(3.2.2)

де X = (x1, …, xn) — вектор змінних, C = (c1, …., cn), B = (b1, …, bm)T, Aj = (a1j, …, amj)T, j = 1, …, n — задані вектори, T — знак транспонування, та відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану — Тоді

(3.2.3)

(3.2.4)

де значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов Aj розкладається по ним єдиним чином:

(3.2.5)

(3.2.6)

(3.2.7)

де xij - коефіцієнт розкладання. Система умов

(3.2.8)

zk ≥ 0, xj = 0, j = m + 1, …, n, j ≠ k (3.2.9)

при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної xk при русі по цьому проміню дорівнює θ, тоді значення базисних змінних дорівнюють xi(θ). В цих позначеннях рівняння (5) можна представити в вигляді:

(3.2.10)

помноживши рівняння (3) на θ при j = k та віднявши від рівняння (1), отримаємо:

(3.2.11)

Із рівнянь (10-11) отримаємо:

(3.2.12)

Оскільки xi(θ) при θ = 0 визначають план задачі, то найбільше θ, яке не порушує обмеження xi (θ) ≥ 0, визначається із умови:

(3.2.13)

де I = {i | xik > 0}

В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та θ > 0. Значення лінійної форми при θ = θ0 визначається із рівнянь (9), (4), (2)

(3.2.14)

де Δk = zk — ck. Очевидно, Δj = 0 для j = 1, …, m.

Нехай — початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:

1. Знайти Δk = minjΔj. Якщо Δk = 0, тоді план, який розглядається оптимізовано; якщо Δk < 0, вектор Ak вводиться в базис;

2. Знайти θ0 та l для якого , із формули (10). Якщо I = Λ — порожня множина, лінійна форма необмежена зверху; якщо I ≠ Λ вектор Al виводиться із базису;

3. По знайденим l, k обчислити нові значення елементів таблиці по формулам

Перетворення (12) замінює вектор коефіцієнтів Xk = (x1k, …, xmk) на одиничний вектор Xk з xlk = 1. В силу монотонного збільшення x0 повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму. Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу,

(3.2.15)

при обмеженнях

(3.2.16)

(3.2.17)

(3.2.18)

яка містить одиничний базис, який складається із векторів An+1, …, An+m. Цим векторам відповідають штучні змінні із значеннями , i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі , вихідна задача не має розв'язку. Якщо ж та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які по формулам (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z0 може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин bi на bi + εi, де εi достатньо малі, при вдалому виборі εi не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця A-1, обернена до базисної матриці.

3.3 Двоїстий симплекс-метод

Двоїстий симплекс-метод розроблений згодом після прямого симплекс-методу, і який є, по суті, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.

Симплекс метод приміняється для рішення задач с невідємними вільними членами ві і вільні у виборі знаку приведеними коефіцієнтами цільової функції сj. Іноді буває легше знайти базис, який задовільняє ознаку оптимальності (усі сj ≥0), але не задовільняє критерії допуску (не всі ві ≥0). Варіант симплекс метода, який приміняється для рішення таких задач, називається двоїстим симплекс методом. За його допомоги рішаються задачі лінійного програмування виду:

(4.3.1)

де система обмежень має такий вигляд і всі приведені коефіцієнти цільової функції сj ≥0, і=1,n. При цьому умова ві ≥0, і=1,т , не потрібно. Виділену таким методом задачу будемо називати задачею в двоїстій базисній формі. Вона має базисне, але не опорне рішення.

Двоїстий симплекс метод, який приміняється до задачі в двоїстій базисній формі, приводить до послідовності задач із збільшуючим значаченням цільової функції з невідємними коефіцієнтами с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” реалізує сам симплекс метод. Наведемо деякі методи з даного класу:

а) public revisedSimplex(int nv, int nc) – ініціалізує об’єкти класу revisedSimplex: nv (Number of Variables – кількість рівнянь), nc (Number of Constrains – кількість обмежень)

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

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

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

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

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

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

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

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

(4.1)

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

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

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

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

к) public void specifyObjective(float [] coefficients, boolean type) – відповідає за ініціалізацію цільової функції

л) public boolean preprocess(int numberOfVariables, int numberOfConstraints) – функція, заповнення и виведення данних, які ми вводимо на екран.

м) public void SetCostForPhaseOne() - визначає можливість вирішення данної задачі.

н) public float Dot (float []row, float []col, int size) - підраховування суми:

(4.2)

о) public void reset(int numberOfVariables, int numberOfConstraints) – функція, яка закриває поточне вирішення задачі і дає можливість вести нові початкові дані.

7. Модуль „enterDataFrame.java” Модуль за допомогою якого дані, які вводить користувач присвоюються виділеним змінним. Тобото проводить їх ініціалізацію.

5. Технічні засоби

У розробленні даної програми було використано обладнання з такими характеристиками: а) Процесор: Intel Pentium 4, 1,8 Ггц; б) ОЗУ: 256 Мб; в) HDD: 40 Гб; г) Відеокарта – GeForce 5500 – 128 Mб; д) операційна система Windows XP Professional SP2;

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4144
Авторов
на СтудИзбе
666
Средний доход
с одного платного файла
Обучение Подробнее