Наведемо останню симплекс-таблицю

Побудуємо нерівність Гоморі за першим аргументом.

Обраний розв'язковий елемент (4,4)

Отриманий план являється оптимальним і цілочисельним.

Розв'язок: X*(1,7) Fmax*=23;

Відповідь: цілочисельною точкою максимуму даної задачі є точка (1,7)

Завдання 3. Задача дробово-лінійного програмування

Для задачі дробово-лінійного програмування знайти розв'язки геометричним методом і симплекс-методом:

,

Розв?язання геометричним методом

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

f(1;0) = 2/3 f(0;1) = 3/7

Тобто при крутінні прямої проти годинникової стрілки значення цільової функції зменшується.

Використаємо результати обчислень і геометричних побудов з попереднього завдання.

З графіка очевидно, що розв'язок лежить на перетині двох прямих. Для визначення точки перетину прямої І та ІІ розв?яжемо систему з двох рівнянь.

Відповідь: функція набуває максимального значення при x1=6/5, x2=36/5.

Розв?язання симплекс-методом

Перейдемо від задачі дробово-лінійного програмування до задачі лінійного програмування.

Вводим заміну:

Вводим ще одну заміну:

Після замін наша задача має такий вигляд:

Приведемо її до канонічної форми і доповнимо її базисами:

Повернемось до заміни:

x1=0 x2=6

Завдання 4. Транспортна задача

Для заданих транспортних задач скласти математичну модель і розв'язати їх методом потенціалів, використавши для визначення початкового плану метод мінімального елемента або північно-західного кута.

1. Запаси деякого однорідного продукту знаходяться на трьох пунктах постачання (базах) A1, A2, A3 і цей продукт потрiбно доставити в три пункти споживання (призначення) B1, B2, B3. Задача полягає в тому, щоб визначити, яку кiлькiсть продукту потрiбно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовільнити повністю потреби кожного пункту споживання і при цьому сумарна вартiсть перевезень була б мiнiмальною (зворотні перевезення виключаються). Вартість перевезень сij (у грн.) з бази Аi до пункту призначення Bj вказана в таблиці, де також наведені дані про запаси ai (у тонанх) продукту і його потреби (у тонах) bj.

Для даної транспортної задачі не виконується умова балансу , тому введемо додатковий пункт постачання з запасами 840-750=90 і тарифами С4s=0 (i=1,2,3). Тоді одержимо замкнену транспортну задачу, яка має розв'язок. Її математична модель має вигляд:

хi,

j 0, 1 i 4, 1 j 3.

За методом північно-західного кута знайдемо опорний план

Страницы: 1, 2, 3