47543 (572026), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

3. ,

Система обмежень

Скористаємось теоремою

Якщо задача лінійного програмування в канонічній формі (7)-(9) має оптимальний план , то є оптимальним планом двоїстої задачі

, ,

Розв’язок:

F_min^*= 9,6;

Завдання 2. Задача цілочислового програмування

Для задачі із завдання 1, як для задачі цілочислового програмування, знайти розв’язки геометричним методом і методом Гоморі.

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

,

Відповідь:

Розв′язання методом Гоморі

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

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

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

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

Розв’язок: X^*(1,7) F_max^*=23;

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x₁=0 x₂=6

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

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

1. Запаси деякого однорідного продукту знаходяться на трьох пунктах постачання (базах) A₁, A₂, A₃ і цей продукт потрiбно доставити в три пункти споживання (призначення) B₁, B₂, B₃. Задача полягає в тому, щоб визначити, яку кiлькiсть продукту потрiбно перевезти з кожного пункту постачання (бази) до кожного пункту споживання (призначення) так, щоб забезпечити вивезення всього наявного продукту з пунктів постачання, задовільнити повністю потреби кожного пункту споживання і при цьому сумарна вартiсть перевезень була б мiнiмальною (зворотні перевезення виключаються). Вартість перевезень с_ij (у грн.) з бази А_i до пункту призначення B_j вказана в таблиці, де також наведені дані про запаси a_i (у тонанх) продукту і його потреби (у тонах) b_j.

Пункти	Пункти споживання			Запаси
постачання	B1	B2	B3
A1	3	5	7		270
A2	6	9	4		180
A3	11	8	10		300
Потреби	260	280	300

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

х_i,

_j 0, 1 i 4, 1 j 3.

Пункти	Пункти споживання			Запаси
постачання	B1	B2	B3
A1	3	5	7		270
A2	6	9	4		180
A3	11	8	10		300
A4	0	0	0		90
Потреби	260	280	300		840 840

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

Пункти	Пункти споживання			Запаси
постачання	B1	B2	B3
A1	3 260	5 10	7		270
A2	6	9 180	4		180
A3	11	8 90	10 210		300
A4	0	0	0 90		90
Потреби	260	280	300		840 840

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

Характеристики

Список файлов ответов (шпаргалок)