Симплекс-метод, Задачі лінійного програмування

Симплекс – метод 

Нехай задана задача лінійного програмування(ЛП) в загальній формі. Це означає,що потрібно знайти максимум(мінімум) лінійної функції на множині, що задана обмеженнями лінійними функціями.

Означення 1. Запишемо загальну задачу ЛП  в математичному вигляді. Потрібно знайти максимум чи мінімум функції при обмеженнях на змінні , заданих в вигляді ,,, причому для всіх .

Тобто всього маємо p обмежень  зі знаком ,  q обмежень  зі знаком , r обмежень зі знаком =. Загальну  кількість обмежень позначимо через , не враховуючи n обмежень виду . Отже область визначення змінних задається в вигляді совокупності лінійних нерівностей та рівнянь. 

При розвязанні задачі ЛП можливі такі випадки:

1) Розв’язок задачі ЛП існує і єдинний.

2) Розв’язок задачі ЛП не існує, тому що обмеження не сумісні, область допустимих  рішеннь порожня.

3) Розв’язок задачі ЛП не існує, тому що обмеження сумісні, область допустимих рішень не порожня, але необмежена.

4) Розв’язків задачі ЛП існує нескінчена кількість. Геометрично це відповідає випадку, коли площина F йде паралельно одній з граней многогранника. 

Приклад 1.  Потрібно знайти максимум та мінімум функції при обмеженнях. Неважко знайти, що  максимум функції досягається в точці (1,0) і рівний 2, мінімум досягається в точці (0,0) та рівний 0. 

Симплекс-метод реалізується за чотири етапи:

1) Задача ЛП в загальній формі приводиться до задачі ЛП в стандартній формі, яка є більш простою порівнянно з задачею ЛП в загальній формі. 

2) Вибирається очевидне початкове рішення, що завжди легко виконати в задачі ЛП в стандартній формі. Це одна з вершин багатогранника обмежень. В цьому рішенні  маємо не більше ніж m зміних відмінних від нуля, причому кожна з цих змінних рівна , вільному члену обмеження рівності, всі останні рівні нулю. Перші змінні називаються базисними, інші вільними. 

3) Рішення перевіряється на оптимальність, виродженість чи зациклювання. 

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

Кроки 1) та 2) виконується одноразово, кроки 3) та 4) виконуються ітераційно. 

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

Означення 3. В стандарній  формі повинні виконуватись умови:

1) Для всіх виконана умова. 

2) Всі обмеження носять характер рівностей

3) Серед стовпців матриці обмежень можна виділити одиничну матрицю. 

Під час приведення задачі ЛП від  загальної форми до стандартної, як правило, кількість обмежень зростає. 

Приведення задачі ЛП до стандартної форми 

1) Припустимо, що для деяких  викона  умова . Тоді  потрібно змінити  знак коєфіцієнтів та вільного члена цього обмеження  на протилежний. Також треба змінити знак нерівності обмеження на протилежний. Наприклад, нехай обмеження має вигляд   . Після перетворення обмеження матиме вигляд:. Тепер  це обмеження уже буде задовольняти умовам  стандартної форми.

2) Потрібно послідовно перетворити всі обмеження-нерівності на обмеження-рівності. Для цього додають нові змінні, змінють обмеження, їх знаки та цільову функцію.

Розглянемо два випадки

а) Нехай обмеження має знак,  тобто обмеження має вигляд. Якщо кількість зміних рівна n, то  цьому випадку в це обмеження вводять додаткову зміну з номером, а обмеження перетворються так:. Цільову функцію перетворють так. Сенс введення додаткової змінної полягає в тому, що за рахунок неї обмеження-нерівність перетворюється на обмеження-рівність, але значення додадткової змінної не впливає на цільову функцію.

Додаткова змінна має певний економічний сенс: це кількість продукції, яка залишилась на складі, тощо. Вона може входити в остаточне рішення.

б)Нехай обмеження має знак,  тобто обмеження має вигляд:. Якщо кількість зміних рівна n, то  цьому випадку в це обмеження вводять додаткову та штучну  зміні з номерами  та, а обмеження перетворються так:.

Штучна змінна не має економічний сенсу, вона потрібна тільки математично. Тому в остаточне рішення вона не повинна входити. 

Цільову функцію  перетворють так:  якщо шукаємо мінімум. Якщо шукаємо максимум, то  функцію слід перетворити так:.

Сенс введення додаткової змінної (зі знаком мінус) полягає в тому, що за рахунок неї обмеження-нерівність перетворюється на обмеження-рівність, але значення додадткової змінної не впливає на цільову функцію. Що стосується штучної змінної, то вона вводиться для того, щоб зберегти рівність. Коєфіцієнт М -  велика величина, призначення якої  ввести штраф за використання штучної зміної. Тобто в оптимальне рішення штучна змінна входити не може. 

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

Після виконання пункту 1) алгоритму всі обмеження- нерівності перетворяться на обмеження-рівності, кількість зміних зміниться, зрідка кількість обмежень теж змінюється. Позначимо через n кількість зміних в задачі ЛП в стандартній формі, через m кількість обмежень задачі, тепер обов’язково.    В обмеженнях задачі ДП обов’язково можна виділити одиничну матрицю. Задача ЛП приведена до стандартної форми.  

Задача ЛП в загальній формі еквівалентна задачі в стандарній формі, вони повинні мати однакові рішення, якщо відкинути додаткові та штучні змінні. 

Приклад 1. Знайти мінімум для функціїпри обмеженнях на змінні. Перетворення здійснюємо за загальним алгоритмом:

1) спочатку міняємо знаки коєфіцієнтів, вільного члена та знак нерівності в останьому обмежені: всі інші обмеження залишаємо без змін.

2) Вводимо додаткові та штучні змінні в обмеження-нерівності для того, щоб перетворити їх в обмеження-рівності:

а) Вводимо додаткову зміну  в перше обмеження: ;

б) Вводимо додаткову та штучну зміні  в друге обмеження: ;

в) Вводимо додаткову та штучну зміні  в трете обмеження: ;

г) Вводимо додаткову та штучну зміні  в четверте(уже змінене) обмеження.

Матриця обмежння може бути записана так: 

Тепер треба змінити цільову функцію: . Зауважимо, що число зміних зросло з двох до девяти, число обмежень залишилось незміним. 

Тепер потрібно вибрати початкове базисне(пояснення нижче)  рішення ЛП. Для стандартної форми ЛП це легко зробити. В кожному обмеженні-рівняні обов’язково є змінна  з коєфіцієнтом +1. Дійсно, в випадку а) це додаткова зміна, в випадку б) це штучна зміна. В якості початкового рішення задачі ЛП вибирається , всі інші рівні нулю. В попередньому прикладі в якості початкового рішення виберемо базисні змінні:, вільні змінні: . Тепер стає зрозумілим сенс введення додаткових та штучних зміних: вони забезпечують існування одиничної матриці та зручний спосіб формування початкового базисного рішення. 

Основні факти з теорії лінійного програмування 

1) Область обмежень задачі ЛП – опуклий многограник.

2) Екстремуми задачі  ЛП досягаються тільки в кутових точках цього многораника.

3) Завжди можна перевести загальну задачу ЛП в еквівалентну їй стандартну задачу ЛП. Це означає, що екстремуми цих задач будуть співпадати, в розв’язок не будуть входити штучні зміні(додаткові можуть). Причому для стандартної задачі ЛП завжди буде n≥m. Тут m – кількість обмежень, n – кількість зміних стандартної  задачі ЛП.

4) Всі кутові точки стандартної невиродженної задачі ЛП мають таку структуру – m деяких зміних будуть більші від нуля, інші n-m зміних рівна нулю. Для виродженої задачі  кількість зміних, рівних нулю, може бути більшою ніж n-m. В подальшому зміні зі значенням більшим від нуля будуть називатись базисними, зі значенням рівним нулю – вільними.  

З пункту 4) випливає примітивний спосіб отримання кутових точок. Треба в СЛАР , i=1,m вибрати m стовпців з неспівпадаючими номерами, назовемо їх базисними,  будемо позначати з верхнім   індексом b, а вільні змінні з індексом v. Будемо вважати вільні зміні  рівними нулю, базисні змінні треба визначити.

Тоді , Якщо  детермінант матриці відміний від нуля, то розв’яжемо СЛАР  m*m та отримаємо рішення. Перевіримо, чи буде для всіх x_i≥0. Якщо так, то це кутова точка, якщо ні – рішення відкидаємо. Всього можна вибрати базисні способами. Якщо n=200, m=50, то потрібно розвязати приблизно  4.5385*10⁴⁷ СЛАР m=50. Такий метод не може бути реалізований. 

Далі потрібно виконати перевірку базисного рішення на оптимальність. 

Критерій оптимальності рішення. 

Будемо позначати базисні змінні  з індексом b, а вільні змінні з індексом v.

Цільову функцію запишемо в вигляді:

Базисні змінні можна записати в вигляді:  за рахунок наявності одиничної матриці. Тут індекс v в  означає, що вибрані тільки ті стовпці матриці обмежень, які відповідають вільним зміним.   Очевидно, що , тепер значення базисних змінних можна підставити в цільову функцію . Останню суму можна перетворити: .  Тут поміняли порядок підсумовування в останій двійній сумі,  та введенні позначення:,

Тепер цільову функцію можна записати так:.

Ознака оптимальності:

1) Якщо шукаємо мінімум цільової функції, а всі величини , то цей мінімум уже досягнуто при останіх значеннях базисних змінних, бо якщо значення вільних зміних будуть більші від нуля, то  сума збільшиться.

2) Якщо шукаємо максимум цільової функції, а всі величини , то цей максимум уже досягнуто при останіх значеннях базисних змінних, бо якщо значення вільних зміних будуть більші від нуля, то  сума зменьшиться. 

Приклад 2. Знайти мінімум для функціїпри обмеженнях на змінні

Вершини області:

1)х₁=10/7,х₂=10/7, F(x)=130/7=18.571;

2)х₁=5,х₂=0, F(x)=35;

3)х₁=6,х₂=0, F(x)=42;

4)х₁=6,х₂=5, F(x)=72;

5)х₁=0,х₂=5, F(x)=30;

Перетворення здійснюємо за загальним алгоритмом:

1) Вводимо додаткові та штучні змінні в обмеження-нерівності для того, щоб перетворити їх в обмеження-рівності:

а) Вводимо додаткову та штучну зміні   в перше обмеження: ;

б) Вводимо додаткову та штучну зміні  в друге обмеження:;

в) Вводимо  додаткову  зміну  в трете обмеження: ;

г) Вводимо додаткову  зміну  в четверте обмеження: ;

Матриця обмежння може бути записана так: 

Тепер треба змінити цільову функцію: .

Число зміних зросло з двох до восьми, число обмежень залишилось незміним.

В  якості початкового рішення виберемо базисні змінні:, вільні змінні: .Для пошуку мінімуму покладемо М=1000,  велике додатне число.

Ітерація 1

Заповнимо таблицю:

Заповнюємо строчку G_J тільки для вільних зміних, це Х₁, Х₂, Х₃, Х₅:

1)G₁=(2*1000+5*1000+1*0+0*0)-7=6993.

Тут С₁=7, А₁₁=2, А₂₁=5 А₃₁=1, А₄₁=0.

2)G₂=(2*1000+5*1000+0*0+1*0)-6=6994;

3)G₃=(-1*1000+0*1000+0*0+0*0)-0=-1000;

4)G₅=(0*1000-1*1000+0*0+0*0)=-1000;

Значення функції в початковій вершині рівне: F=10*1000+10*1000+6*0+5*0=20000

Треба перейти до наступної вершини багатогранника.

Так як ми шукаємо мінімум, то виберемо  з усіх G_J тільки ті, для яких G_J>0, серед них найбільше, це G₂. Отже будемо вводити в базис зміну X₂.

Тепер треба вибрати ту базисну змінну, яку потрібно вивести з базису.

В стовпці з номером 2 виберемо  мінімальну величину тільки серед значень. Це рядок з номером один, . Отже будемо виводити з базису  змінну з номером 1, це X₄ , ця змінна далі буде вільною, отже тепер  X₄=0.

Тепер треба перетворити обмеження так, щоб коєфіцієнт при X₂ був відміний від нуля тільки в другому рядку:

Ітерація 2.

Треба перейти до наступної вершини багатогранника.

Так як ми шукаємо мінімум, то виберемо  з усіх G_J тільки ті, для яких G_J>0, серед них найбільше - G₁. Отже будемо вводити в базис зміну X₁.

Треба вибрати ту базисну змінну, яку потрібно вивести з базису.

В рядку з номером 1 виберемо  мінімальну величину тільки серед значень .  Це рядок з номером 2. Будемо виводити з базису  змінну з номером 2, це X₆, ця змінна далі буде вільною, отже тепер  X₆=0.

Ітерація 3.

Всі G_J при вільних зміних менше нуля. Отже мінімум досягнуто в точці

Х₂=1.429, Х₁=1.429, Х₇=4.571, Х₈=3.571, Х₃=0, Х₄=0, Х₅=0 Х₆=0. В рішення не входять штучні змінні, додаткові змінні цільову функцію не міняють, кількість відміних від нуля базисних зміних рівна кількості обмежень. Отже, мінімум єдиний. Рішення за допопмогою симплекс-методу співпало з графічним.

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

Перетворення здійснюємо за загальним алгоритмом:

1) Вводимо додаткові та штучні змінні в обмеження-нерівності для того, щоб перетворити їх в обмеження-рівності:

а) Вводимо додаткову та штучну зміні   в перше обмеження: ;

б) Вводимо додаткову та штучну зміні  в друге обмеження:;

в) Вводимо  додаткову  зміну  в трете обмеження: ;

г) Вводимо додаткову  зміну  в четверте обмеження: ;

Матриця обмежння може бути записана так:

Тепер треба змінити цільову функцію:.

Число зміних зросло з двох до восьми, число обмежень залишилось незміним.

В  якості початкового рішення виберемо базисні змінні:, вільні змінні: . Покладемо М=-1000 (велике відємне число).

Ітерація 1.

Заповнимо таблицю:

Заповнюємо строчку G_J тільки для вільних зміних, це Х₁, Х₂, Х₃, Х₅:

1)G₁=(-2*1000-5*1000+1*0+0*0)-7=-7007.

Тут С₁=7, А₁₁=2, А₂₁=5 А₃₁=1, А₄₁=0.

2)G₂=(-2*1000-5*1000+0*0+1*0)-6=-7006;

3)G₃=(1*1000+0*1000+0*0+0*0)-0=1000;

4)G₅=(0*1000+1*1000+0*0+0*0)=1000;

Значення функції в початковій вершині рівне: F=-10*1000-10*1000+6*0+5*0=-20000. Будемо послідовно покращувати значення цільової функції. Для цього будемо виводити з базису одну змінну, замість неї введемо теж одну вільну змінну. Тепер виникає два питання:

1)Яку вільну  змінну вводити  в базис?

2)Яку базисну змінну виводити з базису?

Цільову функцію можна виразити через  вільні змінні так: . Тут  введенні позначення:, .

Для того, щоб максимально збільшити цільову функцію треба вибрати мінімальний коєфіцієтнт, для якого  , та ввести цю змінну в базис. Тоді цільова функція збільшиться максимально.

Так як ми шукаємо мінімум, то виберемо  з усіх G_J тільки ті, для яких G_J<0, серед них найменше - G₁. Отже будемо вводити в базис зміну X₁.

Тепер треба вибрати ту базисну змінну, яку потрібно вивести з базису.

Для цього розглянемо рівності обмеження стандартної ЗЛП:

В першому стовпці  потрібно отримати тільки один коефіцфіцієт 1, всі повинні інші рівні бути рівні нулю. Будемо перетворювати систему за допомогою формул виключення Жордана(точно так як в прямому ході метода Гауса).

Якщо за допомогою першого рядка виключити змінну Х₁ з усіх інших рядків, то,  наприклад, отримаємо , але ж повинно бути завжди! Аналогічно,  якщо за допомогою третього  рядка виключити змінну Х₁ з усіх інших рядків, то,  наприклад, отримаємо ,, знову порушимо умову  . Зрозуміло також, що розглядати потрібно тільки ті рядки, де буде  , четвертий рядок теж не підходить.

Залишається другий рядок обмежень, отже виводимо з базису другу по рахунку змінну, це змінна Х₆.

(Теж саме, але трохи інакше, скороченно)

В стовпці з номером 1 виберемо  мінімальну величину тільки серед значень .  Це рядок з номером 2, . Отже будемо виводити з базису  змінну з номером 2, це X₆ , ця змінна далі буде вільною, отже тепер  X₆=0.

Тепер треба перетворити обмеження так, щоб коєфіцієнт при X₁ був відміний від нуля тільки в другому рядку.

Ітерація 2.

Значення функції в  вершині рівне: F=-6*1000*+2*7+4*0+5*0=-5986.

Треба перейти до наступної вершини багатогранника. Виберемо  з усіх G_J тільки ті, для яких G_J<0, серед них найменше - G₂. Отже, будемо вводити в базис зміну X₂.

Треба вибрати ту базисну змінну, яку потрібно вивести з базису.

В стовпці з номером 2 виберемо  мінімальну величину тільки серед значень .  Це рядок з номером 1. Отже будемо виводити з базису  змінну з номером 1, це X₄, ця змінна далі буде вільною, отже  тепер X₄=0.

Тепер треба перетворити обмеження так, щоб коєфіцієнт при X₂ був відміний від нуля тільки в першому рядку:

Ітерація 3.

Значення функції в  вершині рівне: F=18.57

Треба перейти до наступної вершини багатогранника. Виберемо  з усіх G_J тільки ті, для яких G_J<0, серед них найменше - G₅ Отже, будемо вводити в базис зміну X₅

Треба вибрати ту базисну змінну, яку потрібно вивести з базису.

В стовпці з номером 5 виберемо  мінімальну величину тільки серед значень .  Це рядок з номером 1. Отже будемо виводити з базису  змінну з номером 1, це X₂, ця змінна далі буде вільною, отже  тепер X₂=0.

Тепер треба перетворити обмеження так, щоб коєфіцієнт при X₅ був відміний від нуля тільки в першому рядку.

Ітерація 4.

Значення функції в  вершині рівне: F=35

Треба перейти до наступної вершини багатогранника. Виберемо  з усіх G_J тільки ті, для яких G_J<0, серед них найменше - G₃ .Отже, будемо вводити в базис зміну X₃

Треба вибрати ту базисну змінну, яку потрібно вивести з базису.

В стовпці з номером 3 виберемо  мінімальну величину тільки серед значень .  Це рядок з номером 3. Отже будемо виводити з базису  змінну з номером 3, це X₇, ця змінна далі буде вільною, отже  тепер X₇=0.

Тепер треба перетворити обмеження так, щоб коєфіцієнт при X₃ був відміний від нуля тільки в третьому рядку.

Ітерація 5.

Значення функції в  вершині рівне: F=42

Треба перейти до наступної вершини багатогранника. Виберемо  з усіх G_J тільки ті, для яких G_J<0, серед них найменше - G₂ .Отже, будемо вводити в базис зміну X₂.

Треба вибрати ту базисну змінну, яку потрібно вивести з базису.

В стовпці з номером 2 виберемо  мінімальну величину тільки серед значень .  Це рядок з номером 4. Отже будемо виводити з базису  змінну з номером 4, це X₈, ця змінна далі буде вільною, отже  тепер X₈=0.

Тепер треба перетворити обмеження так, щоб коєфіцієнт при X₂ був відміний від нуля тільки в четвертому рядку.

Ітерація 6.

Всі G_J при вільних зміних быльше нуля. Отже максимум досягнуто в точці

Х₅=30, Х₁=6, Х₃=27, Х₂=5, Х₄=0, Х₆=0, Х₇=0, Х₈=0. В рішення не входять штучні змінні, додаткові змінні цільову функцію не міняють, кількість відміних від нуля базисних зміних рівна кількості обмежень. Отже, максимум єдиний. Рішення за допопмогою симплекс-методу співпало з графічним. 

Потрібно проаналізувати ті виключення з алгоритму, що можуть виникнути при виконанні алгоритму.

1) Якщо при пошуку максимуму, для всіх j, для яких виконано  , всі , то це означає, що область пошуку рішень необмежена.

2) Якщо при пошуку мінімуму, для всіх j для яких виконано  ,  всі , то це означає, що область пошуку рішень необмежена.

3) Якщо в оптимальне рішення входять штучні змінні, то це означає, що система обмежень несумісна.

4) Якщо для вільної , то це означає, що розязок задачі ЛП не єдинний. 

Покращення рішення задачі ЛП 

Процесс поліпшення розвязку задачі полягає в наступному:

1) Підрахувати цільову функцію та величини.

2) Перевірити  рішення на оптимальність. Якщо шукаємо максимум цільової функції, а всі величини , то цей максимум уже досягнуто при поточних значеннях базисних змінних. Якщо шукаємо мінімум цільової функції, а всі величини, то цей мінімум уже досягнуто при поточних значеннях базисних змінних. Якщо це твердження несправедливо, то значення цільової функції можна покращити – збільшити якщо ми шукаємо максимум, або зменшити, якщо шукаємо мінімум.

3) Якщо рішення не оптимальне, то потрібно одну з базисних зміних вивести з базису, а одну з вільних зміних ввести в базис. При цьому може зясуватись, що має місце один з випадків виродженної задачі ЛП:

а) Область допустимих  рішеннь порожня;

б) Область допустимих рішень не порожня, але необмежена;

в) Розвязків задачі ЛП існує нескінчена кількість.

Потрібно знайти номер базисної змінної, яку потрібно вивести з базису та номер вільної змінної, яку потрібно ввести в базис. Крім того, потрібно забезпечити перетворення матриці обмежень, що відповідає цим діям.

Припустимо що ми шукаємо максимум. Будемо розглядати тільки ті значення для яких виконана умова(такі значення обов’язково знайдуться) та в рядку матриці обмежень обвязково є хоча б один невідємний елемент. Нехай к – номер найбільшого значення , що задовольняє цим умовам.

Для випадку пошуку мінімуму діємо аналогічно, але розглядаємо множину, для яких в рядку матриці обмежень обов’язково є хоча б один невідємний елемент, тепер к – номер найменшого  значення , що задовольняє цим умовам. Нехай такий номер к знайденно.

Номер k - це номер вільної змінної, яка буде введена в базис. Тепер в стовпці k шукаємо мінімальну величину тільки серед значень  . Номер рядка d в якому для якого величина   мінімальна – це номер базисної змінної, яку потрібно вивести з базису. Останнім етапом поліпшення рішення задачі ЛП є перетворення матриці обмежень за формулами Жордана:

для всіх рядків, крім рядка d. Для цього рядка формула перетворення виконують таким чином:. Крім того . Потім потрібно виконати дії .Очевидно, що суть  перетворення матриці полягає в тому, що рівняння з номером d знаходимо змінну з номером і підставляємо її в усі інші рівняння системи.

Тепер потрібно проаналізувати ті виключення з алгоритму, що можуть виникнути при виконанні алгоритму.

1) Якщо для всіх j для яких виконано,  при пошуку максимуму всі , то це означає, що область пошуку рішень необмежена. Аналогічно, якщо для всіх j для яких виконано  ,  при пошуку мінімуму всі , то це означає, що область пошуку рішень необмежена.

2) Якщо в оптимальне рішення входять штучні змінні, то це означає, що система обмежень несумісна.

3) Якщо для вільної, то це означає, що розязок задачі ЛП не єдинний.

Тепер опишемо реальний алгоритм розвязання задачі ЛП

Алгоритм симплекс-метода

1) Введення даних.  Значення вводяться з текстового файлу, в першому рядку значення n,m, minmax. Тут n - число змінних, m – обмежень, minmax – ознака пошуку мінімума/максимума. Якщо minmax=0 – потрібно знайти мімімум, якщо minmax=1 треба знайти максиум. Далі розташовані m рядків, що описують обмеження, спочатку коефіцієнти, потім знак обмеження(тільки <,>,=), далі значення вільного члена. Останій рядок – значення коефіцієнтів лінійної функції. Наприклад, нехай потрібно знайти мінімум фукції при обмеженнях. В текстовому файлі це буде описано так:

2 2 0

1 1 < 1

1 2 < 1.5

2 1

2) Виключення обмежень рівностей. Перетворення обмежень-нерівностей на обмеження рівності. Кількість невідомих позначимо через kolneizv(в попередньому тексті ця змінна позначенна як n).  Вводиться додатковий масив vidperem, де для кожної змінної вказанно її тип:

{В массиве хранится признак, к какому принадлежит переменная.

1 - обычная переменная;

2 - дополнительная переменная;

3 - искусственая переменная;

Размерность массива kolneizv.} 

3) Доповнюємо масив для нових змінних. В якості великого числа М вибираємо значення 10⁶. Приведення загальної задачі ЛП до стандартної форми завершенно.

4) Вибір  початкового рішення. Введемо масив bazis розмірності m, та priznbaz розмірності n. В масив bazis будемо записувати номери базисних змінних, тобто числа від 1 до n. В масив priznbaz будемо записувати для  базисних змінних 1, для вільних зміних 0. Для  зберігання значень невідомих введемо масив . В якості базисних змінних в кожному обмеженні виберемо штучну змінну, якщо такі змінні присутні в цьому обмеженні, якщо ж ні – то додаткову змінну.  Заповнимо масиви bazis  та priznbaz відповідними значеннями.

Тепер залишилось заповнити масив . Спочатку присвоїмо всім елементам массиву нульове значення. Потім виконаємо цикл:

for i:=1 to kologr do

begin

kt:=bazis[i]; x[kt]:=b[i];

end;

Тут змінна kologr відповідає змінній m. Тепер можна обчислити значення функції для початкового рішешення. Визначимо maxit=5*m. Далі виконаємо пункт 5) maxit разів, або до тих пір поки процессне буде завершенний достроково. 

5) Рішення перевіряється на оптимальність.  Для цього обчислимо значення для змінних за формулою . Якщо шукаємо максимум, то запамятаємо в масиві nomj ті  номери j, для яких виконанно. Аналогічно в випадку пошуку мінімума запамятаємо в масиві nomj ті  номери j, для яких виконанно. Припустимо, що таких номерів не існує, тоді оптимум досягнуто, потрібно видати повідомлення та завершити процесс. 

Якщо ж масив nomj не поржній, то  відсортуємо масив nomj в відповідності зі значенням масива  , тобто це значення буде ключем для сортування масиву nomj. Це потрібно для того, щоб цільова функція на кожній ітерації змінювалась максимально.

Покладемо  k=nomj[1], потім перевіримо, щоб у k- ому стовпці обовязково знайшовся хоча б один  невідємний елемент  матриці . Якщо такого елемента у k- ому стовпці немає, то покладемо, k=nomj[2] та будемо діяти аналогічно. Якщо для всіх j для яких виконано  ,  при пошуку максимуму всі , то це означає, що область пошуку рішень необмежена. Аналогічно, якщо для всіх j для яких виконано  ,  при пошуку мінімуму всі , то це теж  означає, що область пошуку рішень необмежена.  В цьому випадку потрібно видати відповідне повідомлення та припинити процесс. 

Припустимо, що існує хоча б одне значення k таке, в к-ому рядку існують невідємні елементи. Тоді номер k - це номер тієї вільної змінної, яка буде введена в базис. Тепер в стовпці k шукаємо мінімальну величину але тільки серед значень  . Номер рядка d в якому  величина   мінімальна – це номер базисної змінної, яку потрібно вивести з базису. Перетворюєм матрицю обмежень за формулами:

для всіх рядків, крім рядка d. Для цього рядка формула перетворення виконують таким чином:. Крім того . Потім потрібно виконати дії .Очевидно, що суть  перетворення матриці полягає в тому, що рівняння з номером d знаходимо змінну з номером і підставляємо її в усі інші рівняння системи. Далі виконуємо  дії  модифікації масивів bazis та priznbaz:

kt:=bazis[ki]; bazis[ki]:=kj;

priznbaz[kt]:=0; priznbaz[kj]:=1;

for i:=1 to kolneizv do x[i]:=0;

for i:=1 to kologr do

begin

kt:=bazis[i]; x[kt]:=b[i];

end;

Опис алгоритму симплекс- методу завершенний. Слід ще зауважити, що в цілях перевірки та відлагодження роботи програми була використана ще одна підпрограма. Вона знаходила оптимум цільової функції на густій прямокутній сітці методом перебору. Для кожної точки сітки перевірялись всі обмеження в первісній(не перетворенній формі), оптимальне значення запамятовувалось. Хоча цей спосіб працює досить довго, для невеликого числа змінних результати завжди хороші і допомогать при відладці. На етапі  експлуації ця підпрограма не використовується.

З повагою ІЦ "KURSOVIKS"!