За знайденими l, k обчислити нові значення елементів таблиці за формулами

ПРИКЛАДИ ЕКОНОМІЧНИХ ЗАДАЧ лінійного програмування Задача про суміші Задача про розкрій Транспортна задача Моделювання і методика рішення задач лінійного програмування За знайденими l, k обчислити нові значення елементів таблиці за формулами Вирішення задачі лінійного програмування за допомогою «Пошуку рішень» у середовищі Microsoft Office Excel 2003

25131

знак

таблиц

изображений

Моделювання і методика рішення задач лінійного програмування Читать далее: Вирішення задачі лінійного програмування за допомогою «Пошуку рішень» у середовищі Microsoft Office Excel 2003

3. за знайденими l, k обчислити нові значення елементів таблиці за формулами

$x_{ij}' = \begin{cases}x_{ij} - \frac{x_{lj}}{x_{lk}} x_ik, & \mbox{if } i \neq l; \\\frac{x_{lj}}{x_{lk}}, & \mbox{if } i = l;\end{cases}$ (12)

$i = 1, \dots, m + 1,\quad j = 0, 1, \dots, n$ ,

де $x_{i0} = \bar{x}_i,\; x_{m+1\, 0} = \bar{z}_0,\; x_{m+1\, j} = \Delta_j$ та перейти до виконання операції (1) з новими значеннями всіх x_ij = x'_ij.

Перетворення (12) замінює вектор коефіцієнтів X_k = (x_1k, …, x_mk) на одиничний вектор X_k з x_lk = 1. В силу монотонного збільшення x₀ повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму.

Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу

$\sum_{i=1}^m (- y_{n+i}) \to \max$ ,

при обмеженнях

$\sum_{j=1}^n a_{ij}x_{j} + y_{n+i} = b_i,\quad i = 1, \dots,$

$y_{n+1} \geq 0, i = 1, \dots, m$ ;

$x_j \geq 0, j = 1, \dots, n$ ,

яка містить одиничний базис, який складається із векторів A_n+1, …, A_n+m. Цим векторам відповідають штучні змінні із значеннями $\bar{y}_{n+i} = b_i$ , i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі $\sum_{i=1}^m y_{n+i} > 0$ , вихідна задача не має розв'язку. Якщо ж $\sum_{i=1}^m y_{n+i} = 0$ та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які за формулами (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z₀ може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних $\bar{x}_l$ дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин b_i на b_i + ε_i, де ε_i достатньо малі, при вдалому виборі ε_i не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця A^-1, обернена до базисної матриці.

3. Прикладний розділ

3.1 Вирішення задачі лінійного програмування симплекс-методом

Для розробки математичної моделі задачі позначимо:

x₁ – кількість продукту А;

x₂ – кількість продукту В;

Цільова функція буде мати вид:

Z=x₁+2x₂¦mах

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

3 x₁+3 x₂ <= 15 2 x₁+6 x₂ <= 18 4 x₁<= 16 x₁+2x₂ <= 8 Xj>=0, j=1..2

Зведення задачі до канонічного виду: Zmax = x₁+2x₂ при умовах:

3x₁+3x₂+x₃ = 15 2x₁+6x₂+x₄ = 18 4x₁+x₅ = 16 x₁+2x₂+x₆= 8 Xj>=0, j=1..6

Таблиця 5.

Базис	С	План	1	2	0	0	0	0
X3	0	15	3	3	1	0	0	0
X4	0	18	2	6	0	1	0	0
X5	0	16	4	0	0	0	1	0
X6	0	8	1	2	0	0	0	1
Zj-Cj		0	-1	-2	0	0	0	0

Таблиця 6.

Базис	С	План	1	2	0	0	0	0
X3	0	6	2	0	1	-0,5	0	0
X2	2	3	40238	1	0	40330	0	0
X5	0	16	4	0	0	0	1	0
X6	0	2	40238	0	0	-0,3333	0	1
Zj-Cj		6	-0,3333	0	0	40238	0	0

Таблиця 7.

Базис	С	План	1	2	0	0	0	0
X1	1	3	1	0	40210	-0,25	0	0
X2	2	2	0	1	-0,1667	40269	0	0
X5	0	4	0	0	-2	1	1	0
X6	0	1	0	0	-0,1667	-0,25	0	1
Zj-Cj		7	0	0	40330	40269	0	0

Відповідь: Zmax =7, Xопт =(3 ; 2 ; 0 ; 0 ; 4 ; 1).

Це свідчить про те, що максимальний прибуток підприємства буде дорівнювати 7 грн., а виробництво продукції А і В складає відповідно 3 і 2 одиниці.

Раздел: Информатика, программирование
Количество знаков с пробелами: 25131
Количество таблиц: 7
Количество изображений: 6

Скачать

... програмування та її економіко – математичної моделі, опис функцій і команд у вирішенні задач лінійного програмування засобами Exel, а також рішення конкретної задачі за допомогою ПК. 1. Побудова економіко–математичної моделі Загальна модель задачі математичного програмування має такий вигляд: У структурі моделі (1.1) можна виділити 3 елементи: 1) Набір керованих змінних x1, x2, ... x ...

Скачать

... і (усі сj’ ≥0), але не задовільняє критерії допуску (не всі ві ≥0). Варіант симплекс метода, який приміняється для рішення таких задач, називається двоїстим симплекс методом. За його допомоги рішаються задачі лінійного програмування виду: (4.3.1) де система обмежень має такий вигляд і всі приведені коефіцієнти цільової функції сj’ ≥0, і=1,n. При цьому умова ві ≥0, ...

Скачать

2х1+5х2 + 15х3+ 10х4 досягає максимуму при системі обмежень: Розв'язуємо задачу лінійного програмування симплексним методом. Введемо балансні змінні х5 ≥ 0, х6≥ 0, х7≥ 0. Їх величина поки що невідома, але така, що перетворює відповідну нерівність у точну рівність. Після цього, задача лінійного програмування набуде вигляду: ∫ = 12х1+5х2 + 15х3+ 10х4 → max при ...

Скачать

... – відпускна ціна i-го заводу j-й продукції; - закупівельна ціна i-го заводу j-й продукції, - шуканий обсяг закупівель на i-м заводі j-й продукції. 2.5 Перевірка моделі оптимізації на контрольному прикладі В цьому підрозділі на прикладі підприємства ТОВ "Гермес-Груп" розрахуємо модель (2.4.5) за допомогою електроних таблиць MSEcxel. Цільова функція має вигляд: де - об’єм закупівлі; ...

Главная Новости Рефераты Статьи Вузы

О проекте Соглашение

Наверх

Войти на сайт

Навигация

Похожие работы

0 комментариев

Разделы

Инфо

Следите за новостями