иждень, якщо дохід від продажів однієї деталі типу А і В становить відповідно 1,1 руб. і 1,5 руб.
Таблиця 1 - Вихідні дані
ТіпПроізводственная
Алгоритм симплекс-методу включає наступні етапи:
1) складання 1-го опорного плану;
2) перевірка плану на оптимальність;
) визначення провідних (дозволяють) стовпця і рядка;
) побудова нового опорного плану.
Нехай цільова функція має вигляд:
F = c1 В· x1 + c2 В· x2 + c3 В· x3 + c4 В· x4? min (1)
Тоді система обмежень має вигляд:
a11 В· x1 + a12 В· x2 + a13 В· x3 + a14 В· x4? b1
1, x2, x3, x4? 0 (2)
У систему обмежень вводяться додаткові змінні. Отримують систему обмежень:
a11 В· x1-a12 В· x2-a13 В· x3-a14 В· x4 + y1 =-b1
-a21 В· x1-a22 В· x2-a23 В· x3-a24 В· x4 + y2 =-b2
a31 В· x1-a32 В· x2-a33 В· x3-a34 В· x4 + y3 =-b3
a41 В· x1-a42 В· x2-a43 В· x3-a44 В· x4 + y4 =-b4
еквівалентну вихідної і має кращий вид. Звідси виходить початковий опорний план, який заноситься в симплексну таблицю, види:
Таблиця 2 - Загальний вигляд симплекс-таблиці
БПЗБП-x1-x2-x3-x4y1 y2 y3 y4b1 b2 b3 b4a11 a21 a31 a41a12 a22 a32 a42a13 a23 a33 a43a14 a24 a34 a44F0-c1-c2-c3-c4
Останній рядок таблиці називається індексного або рядком оцінок. У стовпець БП занесені базисні змінні. Стовпець ЗБП містить значення вільних членів, що стоять в системі обмежень (2). p align="justify"> Після складання таблиці проглядаються елементи шпальти вільних членів. Якщо всі вони позитивні, то опорне рішення знайдено і починається етап знаходження оптимального рішення. p align="justify"> Алгоритм знаходження оптимального рішення.
) Проглядається індексна рядок симплексної таблиці, якщо всі оцінки позитивні, то оптимальне рішення задачі знайдено. У цьому рішенні всі небазисні змінні рівні 0, а базисні - значенням стовпця ЗБП. p align="justify">) Якщо ж в індексному рядку є негативні оцінки, то серед них знаходиться максимальна за абсолютною величиною
.
Стовпець називається що дозволяє. Змінну, відповідну дозволяючим стовпцю, слід ввести в базис. p> Для визначення дозволяє елемента вводиться особливий коефіцієнт, званий симплексним ставленням. Рядок з
мінімальним симплексним ставленням буде роздільної. Елемент таблиці, що знаходиться на перетині дозвільних рядка і стовпчика називається що дозволяє елементом, позначається він. Далі виробляється перерахунок симплексной таблиці...
