З використанням симплексного методу

Мета роботи – навчитися розв’язувати задачі лінійного програмування з використанням симплексного методу.

У результаті виконання роботи студент повинен:

ЗНАТИ правила побудови опорних планів;

УМІТИ здійснювати перехід під одного плану до іншого;

МАТИ УЯВЛЕННЯ про виконання критеріїв оптимальності.

Симплексний метод (СМ) – це метод цілеспрямованого перебору опірних розв’язків задачі лінійного програмування (ЛП).

Основний зміст симплекс-методу полягає в наступному:

1) вказати спосіб знаходження початкового опорного розв’язку;

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

3) задати критерій, який дозволяє своєчасно припинити перебір розв’язків на оптимальному розв’язку.

Для використання СМ задача ЛП повинна бути приведена до канонічного вигляду.

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

Додаткова змінна вводиться до цільової функції з нульовим коефіцієнтом, тому не впливає на її значення.

Зауваження. У разі нерівності £ до лівої частини треба додавати змінну, у разі ≥ – віднімати.