Використання симплекс-методу

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Теоретична частина

симплекс програма лінійний програмування

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

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

,

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

відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану -

. Тоді

, (1)

, (2)



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

, (3)

, (4)

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

, (5)

zk ?0, xj =0, j = m +1,…, n, j ? k (6)

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

. (7)

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

. (8)



Із рівнянь (7-8) отримаємо

. (9)

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

. (10)

де I = {i | xik > 0}.

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

,

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

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

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

· знайти и0 та l, для якого , із формули (10). Якщо I = Л - порожня множина, лінійна форма необмежена зверху; якщо I ? Л вектор Al виводиться із базису;

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

 (12)

,

де  та перейти до виконання операції (1) з новими значеннями всіх xij = x'ij.

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

Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу

,

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

;

,

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

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



Завдання. Мінімізувати f (x₁, х₂) = -2x₁ + x₂ при обмеженнях:

х₁ + х₂ ? 6,

-3х₁ + 2х₂ ? 3,

х₁ ? 0, х₂ ? 0.

Розв'язування. Для вирішення даної задачі лінійного програмування симплекс-методом використаємо програму Simplex Win.

Для роботи необхідно встановити необхідний розмір матриці обмежень і ввести дані.

Максимальний розмір вхідних даних - 100 рівнянь і 100 змінних.

Вхідні дані тепер можна зберігати і завантажувати з файлу. Для збереження потрібно заповнити матрицю значеннями і вибрати з меню «Файл» пункт «Зберегти». Для того, щоб завантажити файл з вихідними даними, він повинен мати певний формат: перший рядок містити 2 числа через пропуск - кількість рівнянь і кількість змінних. Наступні рядки містять коефіцієнти рівнянь, знак і праву частину. Далі наступний рядок, що містить тип оптимізаційної задачі (max або min). Останній рядок містить коефіцієнти цільової функції. У каталозі з програмою міститься демонстраційний файл.

У v 1.01 якщо завдання вводиться не в канонічній формі, то додаткові змінні і штучні базиси (а також відповідні їм коефіцієнти цільової функції) додаються автоматично.

Штучні базиси додаються методом множителя, тобто коефіцієнти цільової функції при z₁, z₂… z_n (де z_i - штучний базис) відповідно рівні - М, якщо функція на максимум, і М, якщо функція на мінімум.

У v 2.0 у разі наявності штучних базисів в індексному рядку тепер відображаються значення з M коефіцієнтами.

Розглянуто ситуацію нескінченної безлічі оптимальних планів. Доступна можливість ручного вибору ключового елемента. Використання цієї опції доцільно у випадках, коли стандартний алгоритм не дозволяє вивести з базисів штучний базис, а також у всіх інших ситуаціях, коли необхідно вибрати ключовий елемент, відмінний від стандартного. При використанні цієї функції отримані плани не перевіряються на оптимальність і спільність.

Для зручності користування можна налаштувати ширину полів виводу самостійно.

Можна вибрати режим відображення дробів (звичайні чи десяткові), а також вікно повідомлень, куди виводиться інформація про додавання додаткових змінних, штучних базисів і вибір ключового елемента.

Вікно результатів містить базиси, базисний план (БП), елементи матриці та індексний рядок (ІР)

.



Вихідні дані можуть бути представлені в будь-якому вигляді: цілі числа, звичайні дроби, звичайні дроби з цілою частиною, десяткові дроби.

Для виведення результату в Excel у формі «Результати» потрібно натиснути відповідну кнопку.

У формі «Результати» кнопка «Результат» дозволяє провести рішення задачі в автоматичному режимі і відобразити на екрані тільки останню симплексну таблицю і результат. Всі ітерації відображаються в текстовому полі «Дії».



симплекс програма excel

Редактор підписів стовпців викликається відповідною командою з меню «Налаштування». Редактор дозволяє задавати псевдоніми для змінних і правих частин рівнянь. Останній рядок може містити псевдоніми змінних і правих частин, розділені пробілами.

2. Розв'язання поставленої задачі програмно (написати власну програму для розв'язку)

Для реалізації поставленої задачі я використала мову С та середовище програмування DEV-C++ Version 4.9.9.2.

Оскільки програма є консольною, то для неї потребується тільки можливість виконання програм в режимі MS-DOS, або в середовищі, яке його емулює.

Програма є універсальною, в ній передбачена можливість неіснування розв'язку. Програму можна переписати на C# або Delphi, в такому випадку вона матиме приємний дружній інтерфейс користувача.

Алгоритм розв'язання задачі програмно:

· Зчитуємо кількість змінних.

· Зчитуємо кількість обмежуючих умов.

· Визначаємо, задача на максималізацію чи мінімізацію.

· Зчитуємо циклічно елементи масиву.

· За допомогою Жордано-Гаусових перетворень та перевірок визначаємо min/max.

· Виводимо результат.

Рекомендації користувачу:

· Умова додатності змінних уже врахована.

· Першим рядком матриці повинна бути функція мети з інвертованими знаками біля коефіцієнтів.

· Усі знаки повинні бути «менше рівне», якщо це не так, потрібно їх звести до такого вигляду.

· Уважно звіряйте умову перед введенням матриці.

3. Код програми

#include <stdio.h>

#include <stdlib.h>

#include <locale.h>

#define R 10

#define C 10

 // основний масив та тимчасовий

double arr[R] [C];

double brr[R] [C];

int R_inp, C_inp;

int Ind=1;

int Ptr=1;

 // функція виведення матриці

void Output(void) {

printf («\n\nThe matrix:\n»);

for (int i=0; i<R_inp; i++) {

for (int j=0; j<C_inp; j++)

printf («%7.2lf», arr[i] [j]);

printf («\n»);

}

}

 // функція перевірки на наявність від'ємних елементів у першому рядку

int F_str (void) {

for (int i=0; i<C_inp-2; i++)

if (arr[0] [i]<0)

return 1;

return 0;

}

 // функція копіювання з основної матриці в тимчасову

void Copy (double ar[R] [C]) {

for (int i=0; i<R_inp; i++)

for (int j=0; j<C_inp; j++)

brr[i] [j]=arr[i] [j];

}

 // функція, яка виконує числові перетворення (перерахунок матриці)

void Change (int k, int l) {

Copy(arr);



double tmp=arr[k] [l];

arr[k] [l]=1/tmp;

for (int i=0; i<R_inp; i++)

if (i!=k)

arr[i] [l]*=(-1/tmp);

else

continue;

for (int j=0; j<C_inp; j++)

if (j!=l)

arr[k] [j]*=(1/tmp);

else

continue;

for (int i=0; i<R_inp; i++)

if (i==k) continue;

else

for (int j=0; j<C_inp; j++)

if (j==l) continue;

else

arr[i] [j]=brr[i] [j] - (brr[i] [l]*(brr[k] [j]/tmp));

Output();

}

 // функція, яка реалізує основний алгоритм

int Find (void) {

double minB=0;

int B=-1;

double minA=0;

int A=-1;

 // перевірка, чи є в останньому стовпці від'ємні елементи і знаходження найменшого з них

for (int i=1; i<R_inp; i++)

if (arr[i] [C_inp-1]<minB) {

minB=arr[i] [C_inp-1];

B=i;

}

 // продовжуємо шукати координати направляючого елемента

if (B!=-1) {

for (int i=0; i<C_inp-1; i++)

if (arr[B] [i]<minA) {

minA=arr[B] [i];

A=i;

}

if (A==-1) {

printf («There is no\n»);

return 0;

}

 // знайшли - виконуємо перерахунок матриці та робимо знову перевірку

Change (B, A);

Find();

}

 // виводимо мінімум, якщо користувач його шукав

else

if ((B==-1) && (Ind==2)) {

printf («\nMin ->%5.2lf\n», arr[0] [C_inp-1]);

return 0;

}

else

{

 // » чекаємо», поки зникнуть від'ємні елементи в рядку з коефіцієнтами до функції мети

L1:

double minB=999999999;

int B=999999999;

double minA=0;

int A=-1;

printf («\nAll ok\n»);

for (int i=0; i<C_inp-1; i++)

if (arr[0] [i]<minA) {

minA=arr[0] [i];

A=i;

}

int Ptr2=1;

if (A==-1) {

printf («\nMax ->%5.2lf\n», arr[0] [C_inp-1]);

return 0;

}

else {

for (int i=1; i<R_inp; i++) {

if ((arr[i] [A]!=0) && ((abs (arr[0] [A]/arr[i] [A]))<minB)) {

minB=arr[0] [A]/arr[i] [A];

B=i;

Ptr2*=0;

}

}

}

if (Ptr2==1) {

printf («\nFunction dont bordered\n»);

return 0;

}

else

while (F_str()==1) {

Change (B, A);

goto L1;

}

}

return 0;

}

 // вводимо дані

void Input(void) {

printf («Enter number of variables:»);

scanf («%d», &C_inp);

C_inp++;

printf («Enter number restrictions:»);

scanf («%d», &R_inp);

R_inp++;

printf («Find Max (press 1) or Min (press 2)?»);

scanf («%d», &Ind);

printf («Enter the matrix:\n»);

for (int i=0; i<R_inp; i++)

for (int j=0; j<C_inp; j++)

scanf («%lf», &arr[i] [j]);

}

 // головна функція

int main (void) {

Input();

Output();

Find();

system («pause»);

return 0;

}



Висновок

У цій лабораторній роботі я ознайомилася із розв'язанням ЗЛП симплекс-методом та знайшла її розв'язок власноруч на папері, використовуючи Excel із пакета MSOffice 2010, призначений для розв'язку математичних задач та побудови таблиць, написала власну універсальну програму для розв'язку ЗЛП симплекс-методом.

Размещено на Allbest.ru