Етап 1. Наведемо вихідну задачу лінійного програмування до канонічного вигляду. Однак з основних вимог до канонічної формі завдання лінійного програмування є запис функціональних обмежень завдання у вигляді системи лінійних рівнянь невід'ємними правими частинами. Ця вимога випливає з методу Жордана-Гаусса визначення базисного рішення системи лінійних рівнянь. Умова не заперечності правих частин необхідно для того, щоб базисне рішення було допустимим (опорним).
Канонічна форма даного завдання виходить шляхом введення додаткових невід'ємних змінних (базисних або балансних):
В системі (3.6) - x3. x4. x5 і x6 - базисні або балансні змінні, які перетворюють нерівності в рівності. Можна дати наступну економічну інтерпретацію базисних змінних. Наприклад, змінна x3 ≥0 тобто якщо ресурс "молоко" використовуються повністю, то x3 = 0; якщо не повністю, то x3> 0. Таким чином, x3 це надлишок ресурсу "молоко". Подібним чином можна інтерпретувати інші базисні змінні.
Етап 2. Складання першого опорного плану
Заповнюємо перший крок симплексной таблиці
У стовпці 1-7 і рядки 1-5 записуємо коефіцієнти при невідомих і вільні члени системи (3.6). У стовпці базисних змінних записуємо їх позначення. Так як до початку вирішення оцінки базисних змінних невідомих даємо їм значення рівні нулю. Оцінки вільних змінних (кількість продукції, що випускається) приймаються рівними їх значенням в цільовій функції. Рішення задачі лінійного програмування в симплексній таблиці знаходиться в стовпці вільних членів, тобто рішення на першому кроці виглядає як:
Контрольний стовпець служить для перевірки правильності рішення і являє собою добутку коефіцієнтів стовпця вільних членів на оцінки відповідних змінних. Сума цих творів дає значення цільової функції, в даному випадку F (x) = 0
Етап 3. Перевірка плану на оптимальність
Ознакою оптимальності рішення задачі є відсутність позитивних значень в рядку цільової функції. У нашому випадку ця умова не виконується (тобто два позитивних числа-16 і 14). Отже, план не оптимальний і рішення треба продовжити.
Етап 4. Визначення провідних шпальти і рядки
Від першого варіанту плану, в якому ми нічого не випускаємо, переходимо до другого варіанту. Перехід здійснюється наступним чином: визначаються провідний стовпець і рядок (іноді вживається термін «дозволяє») і ведучий елемент.
Якщо подивитися на рядок цільової функції першої ітерації (рядок 5), то там є два позитивних числа -16 і 14, які є коефіцієнтами цільової функції і представляють собою ціни продукції, що випускається (c1 = 16-ціна вершкового морозива; c2 = 14 - ціна шоколадного морозива) тобто на другому кроці ми можемо ввести в план, або випуск вершкового, або шоколадного морозива. Можна ввести в план випуск вершкового морозива, т.к це призводить до великого зростання доходу (16> 14). стовпець відповідний цій цифрі (16) називається ведучим.
З математичної точки зору вибір ведучого шпальти виробляється за правилом: провідний стовпець maх j>
Після вибору ведучого шпальти приступаємо до вибору провідного рядка. Для цього коефіцієнти в стовпці вільних членів ділимо на відповідні коефіцієнти ведучого шпальти:
= 100, і серед них вибираємо мінімальне значення (100). Рядок, що відповідає цьому мінімуму і буде провідною.
Чому вибирається мінімальне значення? Справа в тому, що коефіцієнти в шпальтах 1-6 і рядках 1-4 симплекс- таблиці представляють собою витрата ресурсу на одиницю виробу, а стовпець 7 - це наявність цих ресурсів. Тобто відносини, наприклад 400 / 0,8 = 500. означає, що по ресурсу «молоко» ми можемо випустити 500 кг. вершкового морозива, але при цьому не буде виконуватися рівність 3 системі (3.6), тому що x5 ≥0 Таким чином, ми можемо випускати тільки 100 кг. вершкового морозива і цей рядок (3) стає провідною.
З математичної точки зору вибір провідного рядка проводиться за правилом: ведуча рядок → min>, де a b ij - коефіцієнти ведучого шпальти.
Іноді при виборі провідного рядка виходить кілька рівних. Це може ускладнити вектор провідного рядка і привести до зациклення.
У таких випадках для вибору провідного рядка використовують метод крек, який полягає в наступному. Елементи рядків, які мають однакові найменші значення. діляться на передбачувані дозволяють елементи, а результати заносяться в додаткові рядки. За провідну рядок вибирається та, в якій раніше зустрітися найменше приватне при читанні таблиці зліва на право по стовпцях.