Реферат Побудова та реалізація економіко-математичної МОДЕЛІ

B = (b 1 , ..., b m ) T , A j = (a 1j , ..., a mj ) T , j = 1, ..., n - задані ВЕКТОР, T - знак транспонування, та відмінні від нуля компоненти опорного планом, для полегшення Пояснення розташовані на дерло m місцях вектору X. Базис цього плану -. Тоді

, (1.2)

(1.3),

де - значення лінійної форми на даним плані. Так як вектор-стовпці матріці A лінійно незалежні, будь Який Із векторів умів A j розкладається по них Єдиним чином:

, (1.5)

де x ij коефіцієнт розкладання. Система умів

, (1.6)

z k ≥ 0, x j = 0, j = m + 1, ..., n, j в‰  k (1.7) при заданому k візначає в просторі змінніх задачі промінь, Який виходе Із точки, яка відповідає опорному плану, что розглядається. Нехай Значення змінної x k при Русі по цьом проміню дорівнює Оё, тоді Значення базисних змінніх дорівнюють x i (Оё). У ціх позначені рівняння (1.6) можна представіті в віді

. (1.8)

помножити рівняння (1.4) на Оё при j = k та віднявші від рівняння (1.2), отрімаємо

. (1.9)

Із рівнянь (1.8-1.9) отрімаємо

. (1.10)

Оскількі x i (Оё) при Оё = 0 візначають план задачі, то найбільше Оё, Яке НЕ порушує обмеження x i (Оё) ≥ 0, візначається Із умови

. (1.11)

де I = {i | x ik > 0}.

У силу невіродженості задачі мінімум досягається НЕ більш чем для одного i = J та Оё> 0. Значення лінійної форми при Оё = Оё 0 візначається Із рівнянь (1.10), (1.3), (1.4)

, br/>

де О” k = z k - c k . Очевидно, О” j = 0 для j = 1, ..., m. br/>

Нехай - початковий базис Із m одінічніх векторів. Всі дані задачі запісуються у вігляді симплекс-табліці (Першої ітерації Обчислювальна процеса). Симплекс-алгоритм розв'язання задачі лінійного програмування Складається Із Наступний операцій:

1. найти О” k = min j О” j . Если О” k = 0, тоді план, Який розглядається оптимізовано; ЯКЩО О” k <0, вектор A k вводитися в базис;

2. найти Оё 0 та l, для Якого

,

Із формули (1.10). Если I = О› - порожня множини, лінійна форма Необмежена зверху; ЯКЩО I в‰  О› вектор A l виводу Із базису;

3. по знайдення l, k обчісліті Нові Значення ЕЛЕМЕНТІВ табліці по формулами (1.11)

В 

,

де та перейти до Виконання Операції (1.2) з новімі значень всех x ij = x ' ij .

Перетворення (12) замінює вектор Коефіцієнтів X k = (X 1k , ..., x mk ) на одінічній вектор X k з x lk = 1. У силу монотонного Збільшення x 0 повернення до Вже пройденого планом Неможливо, а Із скінченності кількості опорних планів віпліває скінченність алгоритму. Початковий опорний план з одінічнім базисом можна отріматі, розв'язала опис алгоритму допоміжну задачу

,

при обмеженності

В 

;

,

яка містіть одінічній базис, Який Складається Із векторів A n +1 , ..., A n + m . ЦІМ векторах відповідають штучні змінні Із значень, i = 1, ..., m. Если в оптимальному розв'язку цієї задачі, Вихідна завдання не має розв'язку. Если ж та завдання невіроджена, оптимальний базис Складається позбав Тільки Із векторів віхідної задачі, Які за формулами (1.11) перетворені в одінічну матрицю. Если завдання має невіроджені плани, значення z 0 может НЕ збільшуватісь на ряді ітерацій. Це відбувається через ті, что Значення відповідніх дорівнює нулю та візначається неоднозначно. У таких випадка монотонність методу порушується и может трапітісь заціклювання, тоб, повернення до Вже пройденого базису. Невелика зміна вектора обмежень задачі, яка Полягає в заміні величин b i на b i + Оµ i , де Оµ i Достатньо Малі, при вдалину віборі Оµ i НЕ змінюють множини векторів оптимального опорного плану віхідної задачі и Робить ее невіродженою.

Задача

Мається Аi постачальніків вантажу (I = 1 ... m) та Bj споживачів цього вантажу (j = 1 ... n). Запаси вантажу у постачальніків, Попит споживачів та ВАРТІСТЬ перевезення одініці вантажу від і - го Постачальника до j - го споживача Cij у г.о. надані в табліці. Належить Скласти такий план перевезення вантажу, Який забезпечен бі мінімальні транспортні витрати.

Таблиця 1. - Вхідні дані до транспортної задачі

Постачаль-

ники