Page 14 - 6628

Додаткові змінні x ,..., x у системі (3.3) називаються базисними, решта –
n 1 n k
вільними. Позначивши через x ,..., x відповідні базисні змінні, отримаємо, що
1  k 
канонічному виду задачі співвіднесена точка

x  , b x  b ,..., x  b , x  ...  x  0 . Координати цієї точки задовільняють n
1  1 2  2 k  k k  1  n 
лінійно незалежним умовам: k рівнянням та n - k нерівностям x  для
0
i
вільних змінних. Якщо b  , то точка є допустимою і вершиною.
0
i
Вершина має такі властивості: n – k її координат мають значення 0 (вільні
змінні); k координат мають значення ≥ 0 (базисні змінні); вектор-стовпці
матриці А, що відповідають базисним змінним, лінійно незалежні, тобто
утворюють базис простору R . Невироджена матриця, складена з цих вектор-
k
стовпців, називається базисною матрицею. Вершина, що має такі властивості,
відповідає допустимому базисному розв'язку.
Так як розв'язок задачі досягається у вершині допустимої області, то
достатньо розглянути значення цільової функції тільки у вершинах.
Початковий допустимий базисний розв'язок будується за допомогою базисних
змінних x ,..., x , розміщених у симплекс-таблиці. Допустимій симплекс-
1  k 
таблиці відповідає точка мінімуму, якщо всі коефіцієнти цільової функції
невід'ємні. Якщо цей критерій не виконаний, тобто не всі коефіцієнти цільової
функції невід'ємні, то необхідно перейти до сусіднього допустимого базисного
розв'язку, тобто такого, у якому множини базисних та вільних змінних змінені
на один елемент. Цей процес називають симплекс-кроком або заміною базису.
Суть симплекс-кроку полягає у виключенні одного вектор-стовпця матриці А з
базису і включенні замість нього іншого з допомогою деякої додатньої
величини, що відповідає суті методу Жордана-Гауса.
На підприємстві випускається продукція видів B j (j=1,2,…n), кожен з яких
виробляється на обладнанні виду A i (i = 1,2,…m). Кожен вид обладнання може
випускати всі види продукції, але на випуск одиниці продукції виду В j на
обладнанні виду А i витрачається час а ij (годин). Для кожного із обладнання
виду А i фонд робочого часу (максимально можливий час роботи одного виду
обладнання) становить b i годин. Прибуток від продажу одиниці продукції виду
В j становить с j . Вхідні дані до задачі в загальному вигляді занесені в табл. 3.1.
Потрібно скласти такий план випуску продукції видів B j, щоб прибуток від
реалізації всієї продукції виявився максимальним.
Дана задача відноситься до задач планування оптимального випуску
продукції на підприємстві.
Якщо позначити через x j (j=1,2,...,n) відповідно кількість одиниць
продукції виду B j призначених до випуску, то вищенаведену задачу можна
записати у вигляді системи нерівностей

a x  a x  ... a x  b
11 1 12 2 1n n 1
a x  a x  ... a x  b
21 1 22 2 2n n 2 (3.4)
............................................

a x  a x  ... a x  b ,
m 1 1 m 2 2 mn n m
, ,...,x x x  0,
1 2 n
яка буде відображати суть обмежень при використанні ресурсу.