Введення
Під двоїстої завданням розуміється допоміжна завдання лінійного програмування, формулируемая за допомогою певних правил безпосередньо з умов прямої задачі. Зацікавленість у визначенні оптимального розв'язання прямої задачі шляхом рішення двоїстої до неї завдання обумовлена тим, що обчислення при вирішенні ДЗ можуть виявитися менш складними. Трудомісткість обчислень при вирішенні ЗЛП більшою мірою залежить від числа обмежень, а не від кількості змінних.
Метою курсового проекту є вивчити літературу з обраної теми і навчитися застосовувати на практиці симплекс - метод для вирішення прямої і двоїстої задачі лінійного програмування, а також вирішити двоїсту задачу лінійного програмування за допомогою програми MS Excel.
Курсовий проект складається з вступу, двох розділів і висновку.
У першому розділі розглядаються основні поняття та пропозиції теорії подвійності ЗЛП, види математичних моделей двоїстих задач і їх економічна інтерпретація.
У другому розділі розглядається рішення двоїстої задачі за допомогою програми MS Excel.
1. Двоїстість в лінійному програмуванні
1.1 Прямі та двоїсті задачі лінійного програмування
З економічної точки зору двоїсту задачу можна інтерпретувати так: якою повинна бути ціна одиниці кожного з ресурсів, щоб при заданих кількостях ресурсів b i і величинах вартості одиниці продукції C j мінімізувати загальну вартість витрат? А вихідну завдання визначимо наступним, чином: скільки і якої продукції x j (j = 1,2, ..., n) необхідно зробити, щоб при заданих вартостях C j (j = 1,2, ..., n) одиниці продукції і розмірах наявних ресурсів b i (i = 1,2, ..., n) максимізувати випуск продукції у вартісному вираженні. Більшість завдань лінійного програмування спочатку визначаються як вихідні або двоїсті задачі. Зробивши висновок можна говорити про пару двоїстих задач лінійного програмування.
Кожній задачі лінійного програмування можна певним чином зіставити деяку іншу задачу (лінійного програмування), звану двоїстої або сполученої по відношенню до початкової або прямої задачі. Дамо визначення двоїстої завдання по відношенню до загальної задачі лінійного програмування, що складається, як ми вже знаємо, в знаходженні максимального значення функції:
F = c 1 x 1 + c 2 x 2 + ... c n x n
за умов
Порівнюючи дві сформульовані завдання, бачимо, що двоїста задача складається згідно з такими правилами:
1. Цільова функція вихідної задачі задається на максимум, а цільова функція двоїстої на мінімум.
2. Матриця
складена з коефіцієнтів при невідомих у системі обмежень вихідної задачі, і аналогічна матриця
в двоїстої задачі виходять один з одного транспонування (тобто заміною рядків стовпцями, а стовпців - рядками).
3. Число змінних в двоїстої задачі дорівнює числу обмежень у системі вихідної задачі, а кількість обмежень у системі двоїстої задачі - числу змінних у вихідній задачі.
4. Коефіцієнтами при невідомих у цільовій функції двоїстої задачі є вільні члени в системі вихідної задачі, а правими частинами в співвідношеннях системи двоїстої задачі - коефіцієнти при невідомих у цільовій функції вихідної задачі.
5. Якщо змінна x j вихідної задачі може приймати тільки лише позитивні значення, то j-е умова в системі двоїстої задачі є нерівністю виду «>». Якщо ж змінна x j може приймати як позитивні, так і негативні значення, то 1 - співвідношення в системі представляє собою рівняння. Аналогічні зв'язки мають місце між обмеженнями вихідної задачі і змінними двоїстої задачі. Якщо i - Співвідношення в системі вихідної задачі є нерівністю, то i-я мінлива двоїстої задачі
. В іншому випадку змінна у j може приймати як позитивні, так і негативні значення.
Двоїсті пари завдань зазвичай поділяють на симетричні і несиметричні. У симетричній парі подвійних завдань обмеження прямої задачі і співвідношення двоїстої задачі є нерівностями виду «
«. Таким чином, змінні обох завдань можуть приймати тільки лише невід'ємні значення.
Двоїста задача тісно пов'язана задачею лінійного програмування. Завдання первісна називається вихідної. Рішення двоїстої задачі може бути отримано з рішення вихідної і навпаки. Сполучною фактом цих двох завдань є коефіцієнти C j функції вихідної задачі. Дані коефіцієнти називаються вільними членами системи обмежень двоїстої задачі. Коефіцієнти B i системи обмежень вихідної задачі називаються коефіцієнтами двоїстої задачі. Транспонована матриця коефіцієнтів системи обмежень вихідної задачі є матрицею коефіцієнтів системи обмежень двоїстої задачі.
Розглянемо завдання використання ресурсів. У підприємства є t видів ресурсів у кількості b i (i = 1, 2, ..., m) одиниць, з яких випускається n видів продукції. На виготовлення 1 од. i-й продукції витрачається a ij од. t-гo ресурсу, її вартість становить C j од. Необхідно визначити план випуску продукції, що забезпечує її максимальний випуск у вартісному вираженні. Приймемо за x j (j = 1,2, ..., n) кількість од. j-й продукції і складає максимальне значення лінійної функції
Z = C 1 x 1 + C 2 x 2 + ... + C n x n
Визначимо ресурси, які будуть потрібні для виготовлення товару. Позначимо за одиницю вартості ресурсів одиницю вартості виробленого товару. А через у i (j = 1,2, ..., m) вартість одиниці i-го ресурсу. Тобто вартість усіх витрачених ресурсів, які використовуються для винаходу одиниці j-й продукції, становить. Ціна витрачених ресурсів не повинна перевищувати ціни остаточного товару.
1.2 Основи теореми подвійності
1.2.1. Несиметричні двоїсті задачі
Сформулюємо двоїсту задачу. Необхідно визначити матрицю-рядок Y = (y 1, y 2, ..., y m), яка максимізує лінійну функцію f = YA 0 і задовольняє обмеженням
YA> З (1.1)
Сформулюємо вихідну завдання. Визначити матрицю-стовпець X = (x 1, x 2, ..., x n), яка мінімізує лінійну функцію Z = СХ і. задовольняє обмеженням
AX = A0, Х> 0 (1.2)
Як у вихідної так і в двоїстої задачах А = (a ij) - матриця коефіцієнтів системи обмежень, A 0 = (b 1, b 2, ..., b m) - матриця-стовпець, C = (c 1, c 2, ... , c n) - матриця-рядок. Теорема двоїстості встановлює зв'язок між оптимальними планами пари двоїстих задач.
Теорема двоїстості говорить: якщо з пари двоїстих завдань одну володіє оптимальним планом, то й інша має рішення, причому для екстремальних значень лінійних функцій виконується співвідношення minZ = maxf. Якщо лінійна функція одним із завдань не обмежена, то інша не має рішення
Доказ.
Будемо вважати, що вихідна задача має оптимальний план. План визначено симплексним методом. Можна вважати, що кінцевий базис складається з т перший векторів A 1, A 2, ..., A m.
Будемо вважати, що D є матрицею, складеною з компонент векторів кінцевого базису A 1, A 2., A m Наведена вище таблиця складається з коефіцієнтів розкладання векторів A 1, A 2, ..., A n вихідної системи по векторах базису. У цій таблиці кожному вектору A j відповідає вектор X j.
Використовуючи співвідношення (1.3) та (1.4), отримуємо:
(1.5) A = D, D -1 A =
(1.6) A 0 = DX *; D -1 A 0 = X
(1.7) min Z = C * X *,
(1.8) = C * - C> 0,
де С = (C 1, C 2, ..., C m), С = (C 1, C 2, ..., C m, C m +1, ..., C n), a = (CX 1-C 1; СХ 2 - З 2, ..., CX n-C n) = (Z 1-С; Z 2-C 2; ..., Z n-C n) - вектор, компоненти якого непозитивно, так як вони співпадають з Z j - C j> 0, відповідними оптимальному плану.
Оптимальний план вихідної задачі має вигляд X = D -1 А 0, тому оптимальний план двоїстої задачі шукаємо у вигляді
(1.9) Y = C * D -1
Покажемо, що Y * дійсно план двоїстої задачі. Для цього обмеження (1.2) запишемо у вигляді нерівності YA-С> 0, у ліву частину якого підставимо Y *. Тоді на підставі (1.9), (1.5) і (1.8) отримаємо
Yа-С = С * D -1 А-С = С-С> 0, звідки знаходимо Y * A> З
Так як Y * задовольняє обмеженням (1.2), то це і є план двоїстої задачі. При цьому плані значення лінійної функції двоїстої задачі f (Y) = Y * A 0. Враховуючи співвідношення (1.9), (1.6) і (1.7), маємо
(1.10) f (Y) = Y * A 0 = C * D -1 A 0 = C * X = minZ (X)
Таким чином, значення лінійної функції двоїстої задачі від Y чисельно дорівнює мінімальному значенню лінійної функції вихідної задачі
Доведемо тепер, що Y * є оптимальним планом. Помножимо (1.1) на будь-який план Y двоїстої задачі, а (1.2) - на будь-який план X вихідної задачі: YAX = YA 0 = f (Y), YAX> СХ = Z (X), звідси випливає, що для будь-яких планів Х і Y виконується нерівність
(1.11) f (Y)> Z (X)
Цим же співвідношенням пов'язані і екстремальні значення maxf (Y)> minZ (Х). З останнього нерівності укладаємо, що максимальне значення лінійної функції досягається тільки у разі, якщо maxf (Y) = minZ (X), але це значення f (Y) досягає при плані Y, отже, план Y - оптимальний план двоїстої задачі.
Аналогічно можна довести, що якщо двоїста задача має рішення, то вихідна також володіє рішенням і має місце співвідношення maxf (Y) = minZ (X)
Для доказу другої частини теореми допустимо, що лінійна функція вихідної задачі не обмежена знизу. Тоді з (1.11) випливає, що f (Y) - Y. Це вираз позбавлене сенсу, отже, двоїста задача не має рішень.
Аналогічно припустимо, що лінійна функція двоїстої задачі не обмежена зверху. Тоді з (1.11) отримуємо, що Z (X) + Y. Цей вираз також позбавлено сенсу, тому вихідна задача не має рішень.
Доведена теорема дозволяє при вирішенні однієї з двоїстих задач знаходити оптимальний план іншої. Тут матриця-рядок С = (0; 1; 0; -1; - 3, 0), матриця-стовпець
1 1 2 0 -1 1 0
A 0 = 2 A = 0 -4 1 2 -1 0
3 0 3 0 0 1 1
1 0 0
2 -4 3
A «'= 0 1 0
-1 2 0
1 -1 0
0 0 1
Двоїста задача. Знайти максимальне значення лінійної функції f = y 1 +2 y 2 +5 y 3 при обмеженнях
y 1> 0
2y 1 - 4y 2 + 3y 3> 1,
y 2> 0,
(-Y 1) + 2y 2> (-1),
y 1 - y 2 + y 3 = -3, y 3> 0
Оптимальний план вихідної задачі X = (0; 1 / 3, 0; 11 / 3; 4; 0), при якому отримаємо Z min = -46 / 3. Використовуючи цю ітерацію, знайдемо оптимальний план двоїстої задачі. Згідно з теоремою двоїстості оптимальний план двоїстої задачі знаходиться зі співвідношення Y = C * D -1, де матриця D -1 - Матриця, зворотна матриці, складеної з компонентів векторів, що входять в останній базис, при якому отриманий оптимальний план вихідної задачі. У останній базис входять вектори A 5, A 4, A 2; значить,
1 -1 2
D = (A 5, A 4, A 2) = -1 2 -4
1 0 3
Зворотній матриця D -1 утворена з коефіцієнтів, що стоять в стовпцях A 1, A 3, A 6 четвертій ітерації:
2 1 0
D -1 = -1 / 3 1 / 3 2 / 3
-2 / 3 -1 / 3 1 / 3
З цієї ж ітерації слід С = (-3; -1; 1). Таким чином
2 1 0
Y = С * D -1 = (-3; - 1; 1) -1 / 3 1 / 3 2 / 3
-2 / 3 1 / 3 1 / 3
Y = (-19 / 3; - 11 / 3; - 1 / 3),
тобто y i = С * Х i, де Х i - Коефіцієнти розкладання останньої ітерації, що стоять в стовпцях векторів первісного одиничного базису.
Отже, i-у подвійну змінну можна отримати із значення оцінки (m +1) - го рядка, що стоїть проти відповідного вектора, що входив в початковий одиничний базис, якщо до неї додати відповідне значення коефіцієнта лінійної функції:
у 1 =- 19 / 3 +0 =- 19 / 3; y 2 =- 11 / 3 +0 =- 11 / 3; у 3 =- 1 / 3 +0 =- 1 / 3
При цьому плані maxf =- 46 / 3
Вихідна задача. Знайти матрицю-стовпець Х = (x 1, x 2, ..., x n), яка задовольняє системі обмежень
(1.12). АХ> А 0, Х> 0 і мінімізує лінійну функцію Z = СХ
Систему нерівностей за допомогою додаткових змінних можна перетворити в систему рівнянь, тому будь-яку пару симетричних двоїстих завдань можна перетворити в пару несиметричних, для яких теорема подвійності вже доведена.
Використовуючи симетричність, можна вибрати завдання, більш зручну для вирішення. Обсяг завдання, розв'язуваної за допомогою ЕОМ, обмежений числом включаються рядків, тому завдання, досить громіздка у вихідній постановці, може бути спрощена в двоїстої формулюванні. При обчисленнях без допомоги машин використання подвійності спрощує обчислення.
Очевидно, для того щоб записати двоїсту задачу, спочатку необхідно систему обмежень вихідної задачі привести до виду. Для цього друга нерівність слід помножити на -1.
1.3 Види математичних моделей двоїстих задач
Грунтуючись на розглянутих несиметричних і симетричних двоїстих задач відзначимо, що пари двоїстих задач математичних моделей можуть бути представлені таким чином:
· Симетричні завдання
(1) Вихідна задача Двоїста задача
Z min = CX; f max = Y> A 0;
AX = A 0; YA = С
X> 0 Y> 0
(2) Вихідна задача Двоїста задача
Z max = CX; f min = YA 0;
AX = A 0; YA = С
X> 0 Y> 0
· Несиметричні завдання
(3) Вихідна задача Двоїста задача
Z min = CX; f max = YA 0;
AX = A 0; YA = С
X> 0
(4) Вихідна задача Двоїста задача
Z max = CX; f min = YA 0;
AX = A 0; YA = С
X> 0
Тому до того, як сформулювати двоїсту задачу для даної вихідної, необхідно систему обмежень вихідної задачі перетворити належним чином.
Якщо розглянути перший сімплексною таблицю з одиничним додатковим базисом, тоді перехід до двоїстої задачі не обов'язковий. Це пов'язано з тим, що в стовпцях визначена вихідна завдання, а в рядках - двоїста.
b i є оцінками плану двоїстої задачі. З j є оцінками плану вихідної задачі.
Знайдемо рішення двоїстої завдання з симплексного таблиці. У симплексного таблиці прописана вихідна задача. Також визначимо оптимальний план двоїстої задачі. Також знайдемо і оптимальний план вихідної задачі.
Такий метод прийнято називати двоїстим симплексним методом.
Припустимо потрібно визначити початкову задачу лінійного програмування, яка поставлена в загальному вигляді: мінімізувати функцію Z = СХ при АХ = A 0, Х> 0. Значить в двоїстої задачі слід максимізувати функцію f = YA 0 при YA> С. Нехай визначений наступний базис D = (A 1, А 2, ..., А i, ..., А m), причому в ньому хоча б одна з компонент вектора Х = D -1 A 0 = (x 1, x 2, ..., x i, ..., x m) негативна. Для усіх векторів A j використовується наступне співвідношення Z j-C j> 0 (i = 1,2, ..., n).
Користуючись теоремою двоїстості, Y = С баз D -1 є планом двоїстої задачі. Цей план не оптимальний. Тому що оцінки оптимального плану двоїстої задачі повинні бути невід'ємними і вибраний базис X містить негативну компоненту і не є планом вихідної задачі, а з іншого боку.
Тому, слід виключити з базису вихідної задачі вектор А i, який відповідає компоненті x i <0. Цей вектор відноситься до негативної оцінки, його необхідно включити в базис двоїстої задачі.
Переглядаємо i-й рядок для вибору вектора, що включається в базис вихідної задачі. Тобто якщо рядок не має x ij <0, тоді лінійна функція двоїстої задачі не обмежена на многограннику рішень. Тому немає рішень вихідної задачі.
В іншому випадку для стовпців, які мають негативні значення, визначаємо q 0j = min (x i / x ij)> 0. Також знаходимо вектор, який відповідає minq 0j (Z j-C j) при вирішенні вихідної задачі на максимум, а також maxq 0j (Z j-C j) при значенні вихідної задачі на мінімум.
Знайдений вектор включаємо в базис вихідної задачі. Спрямовуючої рядком визначається вектор, який треба прибрати з базису вихідної задачі.
Під двоїстої завданням розуміється допоміжна завдання лінійного програмування, формулируемая за допомогою певних правил безпосередньо з умов прямої задачі. Зацікавленість у визначенні оптимального розв'язання прямої задачі шляхом рішення двоїстої до неї завдання обумовлена тим, що обчислення при вирішенні ДЗ можуть виявитися менш складними. Трудомісткість обчислень при вирішенні ЗЛП більшою мірою залежить від числа обмежень, а не від кількості змінних.
Метою курсового проекту є вивчити літературу з обраної теми і навчитися застосовувати на практиці симплекс - метод для вирішення прямої і двоїстої задачі лінійного програмування, а також вирішити двоїсту задачу лінійного програмування за допомогою програми MS Excel.
Курсовий проект складається з вступу, двох розділів і висновку.
У першому розділі розглядаються основні поняття та пропозиції теорії подвійності ЗЛП, види математичних моделей двоїстих задач і їх економічна інтерпретація.
У другому розділі розглядається рішення двоїстої задачі за допомогою програми MS Excel.
1. Двоїстість в лінійному програмуванні
1.1 Прямі та двоїсті задачі лінійного програмування
З економічної точки зору двоїсту задачу можна інтерпретувати так: якою повинна бути ціна одиниці кожного з ресурсів, щоб при заданих кількостях ресурсів b i і величинах вартості одиниці продукції C j мінімізувати загальну вартість витрат? А вихідну завдання визначимо наступним, чином: скільки і якої продукції x j (j = 1,2, ..., n) необхідно зробити, щоб при заданих вартостях C j (j = 1,2, ..., n) одиниці продукції і розмірах наявних ресурсів b i (i = 1,2, ..., n) максимізувати випуск продукції у вартісному вираженні. Більшість завдань лінійного програмування спочатку визначаються як вихідні або двоїсті задачі. Зробивши висновок можна говорити про пару двоїстих задач лінійного програмування.
Кожній задачі лінійного програмування можна певним чином зіставити деяку іншу задачу (лінійного програмування), звану двоїстої або сполученої по відношенню до початкової або прямої задачі. Дамо визначення двоїстої завдання по відношенню до загальної задачі лінійного програмування, що складається, як ми вже знаємо, в знаходженні максимального значення функції:
F = c 1 x 1 + c 2 x 2 + ... c n x n
за умов
Порівнюючи дві сформульовані завдання, бачимо, що двоїста задача складається згідно з такими правилами:
1. Цільова функція вихідної задачі задається на максимум, а цільова функція двоїстої на мінімум.
2. Матриця
складена з коефіцієнтів при невідомих у системі обмежень вихідної задачі, і аналогічна матриця
в двоїстої задачі виходять один з одного транспонування (тобто заміною рядків стовпцями, а стовпців - рядками).
3. Число змінних в двоїстої задачі дорівнює числу обмежень у системі вихідної задачі, а кількість обмежень у системі двоїстої задачі - числу змінних у вихідній задачі.
4. Коефіцієнтами при невідомих у цільовій функції двоїстої задачі є вільні члени в системі вихідної задачі, а правими частинами в співвідношеннях системи двоїстої задачі - коефіцієнти при невідомих у цільовій функції вихідної задачі.
5. Якщо змінна x j вихідної задачі може приймати тільки лише позитивні значення, то j-е умова в системі двоїстої задачі є нерівністю виду «>». Якщо ж змінна x j може приймати як позитивні, так і негативні значення, то 1 - співвідношення в системі представляє собою рівняння. Аналогічні зв'язки мають місце між обмеженнями вихідної задачі і змінними двоїстої задачі. Якщо i - Співвідношення в системі вихідної задачі є нерівністю, то i-я мінлива двоїстої задачі
Двоїсті пари завдань зазвичай поділяють на симетричні і несиметричні. У симетричній парі подвійних завдань обмеження прямої задачі і співвідношення двоїстої задачі є нерівностями виду «
Двоїста задача тісно пов'язана задачею лінійного програмування. Завдання первісна називається вихідної. Рішення двоїстої задачі може бути отримано з рішення вихідної і навпаки. Сполучною фактом цих двох завдань є коефіцієнти C j функції вихідної задачі. Дані коефіцієнти називаються вільними членами системи обмежень двоїстої задачі. Коефіцієнти B i системи обмежень вихідної задачі називаються коефіцієнтами двоїстої задачі. Транспонована матриця коефіцієнтів системи обмежень вихідної задачі є матрицею коефіцієнтів системи обмежень двоїстої задачі.
Розглянемо завдання використання ресурсів. У підприємства є t видів ресурсів у кількості b i (i = 1, 2, ..., m) одиниць, з яких випускається n видів продукції. На виготовлення 1 од. i-й продукції витрачається a ij од. t-гo ресурсу, її вартість становить C j од. Необхідно визначити план випуску продукції, що забезпечує її максимальний випуск у вартісному вираженні. Приймемо за x j (j = 1,2, ..., n) кількість од. j-й продукції і складає максимальне значення лінійної функції
Z = C 1 x 1 + C 2 x 2 + ... + C n x n
Визначимо ресурси, які будуть потрібні для виготовлення товару. Позначимо за одиницю вартості ресурсів одиницю вартості виробленого товару. А через у i (j = 1,2, ..., m) вартість одиниці i-го ресурсу. Тобто вартість усіх витрачених ресурсів, які використовуються для винаходу одиниці j-й продукції, становить. Ціна витрачених ресурсів не повинна перевищувати ціни остаточного товару.
1.2 Основи теореми подвійності
1.2.1. Несиметричні двоїсті задачі
Теорема двоїстості:
Система обмежень вихідної задачі в несиметричних двоїстих завданнях визначається як рівність. Двоїста ж завдання задається, як нерівність, причому змінні можуть бути і негативними. Що б простіше розуміти постановку завдання будемо інтерпретувати її в матричній формі.Сформулюємо двоїсту задачу. Необхідно визначити матрицю-рядок Y = (y 1, y 2, ..., y m), яка максимізує лінійну функцію f = YA 0 і задовольняє обмеженням
YA> З (1.1)
Сформулюємо вихідну завдання. Визначити матрицю-стовпець X = (x 1, x 2, ..., x n), яка мінімізує лінійну функцію Z = СХ і. задовольняє обмеженням
AX = A0, Х> 0 (1.2)
Як у вихідної так і в двоїстої задачах А = (a ij) - матриця коефіцієнтів системи обмежень, A 0 = (b 1, b 2, ..., b m) - матриця-стовпець, C = (c 1, c 2, ... , c n) - матриця-рядок. Теорема двоїстості встановлює зв'язок між оптимальними планами пари двоїстих задач.
Теорема двоїстості говорить: якщо з пари двоїстих завдань одну володіє оптимальним планом, то й інша має рішення, причому для екстремальних значень лінійних функцій виконується співвідношення minZ = maxf. Якщо лінійна функція одним із завдань не обмежена, то інша не має рішення
Доказ.
Будемо вважати, що вихідна задача має оптимальний план. План визначено симплексним методом. Можна вважати, що кінцевий базис складається з т перший векторів A 1, A 2, ..., A m.
Будемо вважати, що D є матрицею, складеною з компонент векторів кінцевого базису A 1, A 2., A m Наведена вище таблиця складається з коефіцієнтів розкладання векторів A 1, A 2, ..., A n вихідної системи по векторах базису. У цій таблиці кожному вектору A j відповідає вектор X j.
Використовуючи співвідношення (1.3) та (1.4), отримуємо:
(1.5) A = D, D -1 A =
(1.6) A 0 = DX *; D -1 A 0 = X
(1.7) min Z = C * X *,
(1.8) = C * - C> 0,
де С = (C 1, C 2, ..., C m), С = (C 1, C 2, ..., C m, C m +1, ..., C n), a = (CX 1-C 1; СХ 2 - З 2, ..., CX n-C n) = (Z 1-С; Z 2-C 2; ..., Z n-C n) - вектор, компоненти якого непозитивно, так як вони співпадають з Z j - C j> 0, відповідними оптимальному плану.
Оптимальний план вихідної задачі має вигляд X = D -1 А 0, тому оптимальний план двоїстої задачі шукаємо у вигляді
(1.9) Y = C * D -1
Покажемо, що Y * дійсно план двоїстої задачі. Для цього обмеження (1.2) запишемо у вигляді нерівності YA-С> 0, у ліву частину якого підставимо Y *. Тоді на підставі (1.9), (1.5) і (1.8) отримаємо
Yа-С = С * D -1 А-С = С-С> 0, звідки знаходимо Y * A> З
Так як Y * задовольняє обмеженням (1.2), то це і є план двоїстої задачі. При цьому плані значення лінійної функції двоїстої задачі f (Y) = Y * A 0. Враховуючи співвідношення (1.9), (1.6) і (1.7), маємо
(1.10) f (Y) = Y * A 0 = C * D -1 A 0 = C * X = minZ (X)
Таким чином, значення лінійної функції двоїстої задачі від Y чисельно дорівнює мінімальному значенню лінійної функції вихідної задачі
Доведемо тепер, що Y * є оптимальним планом. Помножимо (1.1) на будь-який план Y двоїстої задачі, а (1.2) - на будь-який план X вихідної задачі: YAX = YA 0 = f (Y), YAX> СХ = Z (X), звідси випливає, що для будь-яких планів Х і Y виконується нерівність
(1.11) f (Y)> Z (X)
Цим же співвідношенням пов'язані і екстремальні значення maxf (Y)> minZ (Х). З останнього нерівності укладаємо, що максимальне значення лінійної функції досягається тільки у разі, якщо maxf (Y) = minZ (X), але це значення f (Y) досягає при плані Y, отже, план Y - оптимальний план двоїстої задачі.
Аналогічно можна довести, що якщо двоїста задача має рішення, то вихідна також володіє рішенням і має місце співвідношення maxf (Y) = minZ (X)
Для доказу другої частини теореми допустимо, що лінійна функція вихідної задачі не обмежена знизу. Тоді з (1.11) випливає, що f (Y) - Y. Це вираз позбавлене сенсу, отже, двоїста задача не має рішень.
Аналогічно припустимо, що лінійна функція двоїстої задачі не обмежена зверху. Тоді з (1.11) отримуємо, що Z (X) + Y. Цей вираз також позбавлено сенсу, тому вихідна задача не має рішень.
Доведена теорема дозволяє при вирішенні однієї з двоїстих задач знаходити оптимальний план іншої. Тут матриця-рядок С = (0; 1; 0; -1; - 3, 0), матриця-стовпець
1 1 2 0 -1 1 0
A 0 = 2 A = 0 -4 1 2 -1 0
3 0 3 0 0 1 1
1 0 0
2 -4 3
A «'= 0 1 0
-1 2 0
1 -1 0
0 0 1
Двоїста задача. Знайти максимальне значення лінійної функції f = y 1 +2 y 2 +5 y 3 при обмеженнях
y 1> 0
2y 1 - 4y 2 + 3y 3> 1,
y 2> 0,
(-Y 1) + 2y 2> (-1),
y 1 - y 2 + y 3 = -3, y 3> 0
Оптимальний план вихідної задачі X = (0; 1 / 3, 0; 11 / 3; 4; 0), при якому отримаємо Z min = -46 / 3. Використовуючи цю ітерацію, знайдемо оптимальний план двоїстої задачі. Згідно з теоремою двоїстості оптимальний план двоїстої задачі знаходиться зі співвідношення Y = C * D -1, де матриця D -1 - Матриця, зворотна матриці, складеної з компонентів векторів, що входять в останній базис, при якому отриманий оптимальний план вихідної задачі. У останній базис входять вектори A 5, A 4, A 2; значить,
1 -1 2
D = (A 5, A 4, A 2) = -1 2 -4
1 0 3
Зворотній матриця D -1 утворена з коефіцієнтів, що стоять в стовпцях A 1, A 3, A 6 четвертій ітерації:
2 1 0
D -1 = -1 / 3 1 / 3 2 / 3
-2 / 3 -1 / 3 1 / 3
З цієї ж ітерації слід С = (-3; -1; 1). Таким чином
2 1 0
Y = С * D -1 = (-3; - 1; 1) -1 / 3 1 / 3 2 / 3
-2 / 3 1 / 3 1 / 3
Y = (-19 / 3; - 11 / 3; - 1 / 3),
тобто y i = С * Х i, де Х i - Коефіцієнти розкладання останньої ітерації, що стоять в стовпцях векторів первісного одиничного базису.
Отже, i-у подвійну змінну можна отримати із значення оцінки (m +1) - го рядка, що стоїть проти відповідного вектора, що входив в початковий одиничний базис, якщо до неї додати відповідне значення коефіцієнта лінійної функції:
у 1 =- 19 / 3 +0 =- 19 / 3; y 2 =- 11 / 3 +0 =- 11 / 3; у 3 =- 1 / 3 +0 =- 1 / 3
При цьому плані maxf =- 46 / 3
1.2.2 Симетричні двоїсті задачі
Різновидом двоїстих задач лінійного, програмування є подвійні симетричні завдання, в яких система обмежень як вихідної, так і двоїстої задач задається нерівностями, причому на двоїсті змінні накладається умова позитивності.Вихідна задача. Знайти матрицю-стовпець Х = (x 1, x 2, ..., x n), яка задовольняє системі обмежень
(1.12). АХ> А 0, Х> 0 і мінімізує лінійну функцію Z = СХ
Систему нерівностей за допомогою додаткових змінних можна перетворити в систему рівнянь, тому будь-яку пару симетричних двоїстих завдань можна перетворити в пару несиметричних, для яких теорема подвійності вже доведена.
Використовуючи симетричність, можна вибрати завдання, більш зручну для вирішення. Обсяг завдання, розв'язуваної за допомогою ЕОМ, обмежений числом включаються рядків, тому завдання, досить громіздка у вихідній постановці, може бути спрощена в двоїстої формулюванні. При обчисленнях без допомоги машин використання подвійності спрощує обчислення.
Очевидно, для того щоб записати двоїсту задачу, спочатку необхідно систему обмежень вихідної задачі привести до виду. Для цього друга нерівність слід помножити на -1.
1.3 Види математичних моделей двоїстих задач
Грунтуючись на розглянутих несиметричних і симетричних двоїстих задач відзначимо, що пари двоїстих задач математичних моделей можуть бути представлені таким чином:
· Симетричні завдання
(1) Вихідна задача Двоїста задача
Z min = CX; f max = Y> A 0;
AX = A 0; YA = С
X> 0 Y> 0
(2) Вихідна задача Двоїста задача
Z max = CX; f min = YA 0;
AX = A 0; YA = С
X> 0 Y> 0
· Несиметричні завдання
(3) Вихідна задача Двоїста задача
Z min = CX; f max = YA 0;
AX = A 0; YA = С
X> 0
(4) Вихідна задача Двоїста задача
Z max = CX; f min = YA 0;
AX = A 0; YA = С
X> 0
Тому до того, як сформулювати двоїсту задачу для даної вихідної, необхідно систему обмежень вихідної задачі перетворити належним чином.
1.4 Двоїстий симплексний метод
Для отримання рішення вихідної задачі можна перейти до двоїстою. А використовуючи оцінки її оптимального плану, можна визначити оптимальне рішення вихідної задачі.Якщо розглянути перший сімплексною таблицю з одиничним додатковим базисом, тоді перехід до двоїстої задачі не обов'язковий. Це пов'язано з тим, що в стовпцях визначена вихідна завдання, а в рядках - двоїста.
b i є оцінками плану двоїстої задачі. З j є оцінками плану вихідної задачі.
Знайдемо рішення двоїстої завдання з симплексного таблиці. У симплексного таблиці прописана вихідна задача. Також визначимо оптимальний план двоїстої задачі. Також знайдемо і оптимальний план вихідної задачі.
Такий метод прийнято називати двоїстим симплексним методом.
Припустимо потрібно визначити початкову задачу лінійного програмування, яка поставлена в загальному вигляді: мінімізувати функцію Z = СХ при АХ = A 0, Х> 0. Значить в двоїстої задачі слід максимізувати функцію f = YA 0 при YA> С. Нехай визначений наступний базис D = (A 1, А 2, ..., А i, ..., А m), причому в ньому хоча б одна з компонент вектора Х = D -1 A 0 = (x 1, x 2, ..., x i, ..., x m) негативна. Для усіх векторів A j використовується наступне співвідношення Z j-C j> 0 (i = 1,2, ..., n).
Користуючись теоремою двоїстості, Y = С баз D -1 є планом двоїстої задачі. Цей план не оптимальний. Тому що оцінки оптимального плану двоїстої задачі повинні бути невід'ємними і вибраний базис X містить негативну компоненту і не є планом вихідної задачі, а з іншого боку.
Тому, слід виключити з базису вихідної задачі вектор А i, який відповідає компоненті x i <0. Цей вектор відноситься до негативної оцінки, його необхідно включити в базис двоїстої задачі.
Переглядаємо i-й рядок для вибору вектора, що включається в базис вихідної задачі. Тобто якщо рядок не має x ij <0, тоді лінійна функція двоїстої задачі не обмежена на многограннику рішень. Тому немає рішень вихідної задачі.
В іншому випадку для стовпців, які мають негативні значення, визначаємо q 0j = min (x i / x ij)> 0. Також знаходимо вектор, який відповідає minq 0j (Z j-C j) при вирішенні вихідної задачі на максимум, а також maxq 0j (Z j-C j) при значенні вихідної задачі на мінімум.
Знайдений вектор включаємо в базис вихідної задачі. Спрямовуючої рядком визначається вектор, який треба прибрати з базису вихідної задачі.
Припустимо, що q 0j = min (x i / x ij) = 0, тобто x i = 0, тоді x ij вибирається як дозволяє елемент, але лише тоді, коли x ij> 0.
Даний підхід до вирішення завдання не призводить до зростання кількості негативних компонент вектора X. Поки не буде отримано Х> 0, процес не припиняється.
Визначаючи оптимальний план двоїстої задачі, знаходимо і оптимальний план вихідної задачі.
Використовуючи при вирішенні, алгоритм двоїстого симплексного методу умова Z j-C j> 0 допускається не враховувати, поки не будуть виключені всі х i <0.
Звичайним симплексним методом визначається оптимальний план. Цей метод зазвичай використовується за умови, що всі х i <0. Щоб перейти до плану вихідної, завдання за одну ітерацію треба визначити q 0j = max (x i / x ij)> 0.
Завдання лінійного програмування можна вирішувати двоїстим симплексним методом. Системи обмежень в задачах при позитивному базисі мають вільні члени будь-якого знаку. Двоїстий симплексний метод дозволяє значно зменшити розміри симплексного таблиці та кількість перетворень системи обмежень.
2. Розробка програми
2.1 Постановка завдання
Необхідно спланувати роботу швейної майстерні на деякий період. Встановлено перелік продукції, що випускається, відома ринкова ціна кожного продукту. Для виробництва продукції використовуються ресурси: матеріал, нитки, гудзики, праця закрійників, швачок-моторісток і т.д. Встановлено повний перелік цих ресурсів і загальна кількість кожного ресурсу, яке може бути витрачено в плановому періоді. Відомий витрата кожного ресурсу на одиницю кожного продукту. Необхідно визначити, скільки кожної продукції потрібно робити, щоб сумарна ринкова ціна всієї продукції (випуск, виручка) була найбільшою.
Введемо наступні позначення:
i = 1, ..., m - номери (індекси) використовуваних ресурсів;
- Запас i-го ресурсу, тобто допустима витрата i-го ресурсу в плановому періоді; інша назва - обмеження по ресурсу i;
j = 1, ..., n - номери (індекси) продуктів;
- Ринкова ціна j-го продукту;
- Витрата i-го ресурсу на виробництво одиниці j-го продукту;
- Плановий обсяг виробництва j-го продукту, величина невідома, її потрібно знайти в процесі виконання завдання. Вихідні дані задачі запишемо у вигляді матриці.
Рис. 2
Кожен рядок матриці відповідає одного ресурсу, кожен стовпець - одному продукту. Праворуч від кожного рядка записана величина обмеження по ресурсу (b 1, ..., b i, ..., b m); внизу кожного стовпця - ціна продуктів (з 1, ..., с j, ..., с m).
У кожній клітинці матриці записані так звані технологічні коефіцієнти a ij, показують витрата i-го ресурсу на виробництво одиниці j-го продукту.
Запишемо конкретний числовий приклад
Рис. 3
2.2 Побудова математичної моделі
Тепер приступимо до створення математичної моделі, тобто до математичного запису завдання.
Цільова функція:
Обмеження:
x 1 ³ 0;
x 2 ³ 0;
x 3 ³ 0.
2.3 Опис рішення даного завдання
Вирішимо поставлену вище задачу із застосуванням EXCEL.
Зміст осередків:
B1: D1 - імена продуктів (технологічних способів);
A2: A4 - імена ресурсів;
B2: D4 - технологічні коефіцієнти (витрати ресурсів при поодиноких интенсивностях технологічних способів);
B6: D6 - ціни продуктів;
B8: D8 - змінні;
F2: F4 - запас ресурсів;
G2: G4 - планові витрати ресурсів, виходять в результаті рішення;
G6 - значення цільової функції, виходить в результаті рішення.
Формули для обчислень:
G2 = СУММПРОІЗВ (B $ 8: D $ 8; B2: D2);
G3: G4 - копіюються з G2;
G6 = СУММПРОІЗВ (B8: D8; B6: D6).
Запишемо формули в комірки G2: G4. Встановити курсор на G2. На панелі інструментів вибрати значок формул (f). З'являться два вікна. У вікні «категорія» вибрати «математичні», потім у вікні «функція» вибрати «СУММПРОІЗВ». З'явиться вікно «СУММПРОІЗВ». У ньому потрібно вказати, де розташовуються операнди. Перший операнд - рядок B $ 8: D $ 8, другий операнд - стоку B2: D2. У комірки G3: G4 формулу скопіювати з G2. Аналогічним чином записати формулу цільової функції в клітинку G6. Тепер потрібно вказати інші умови розв'язання задачі. Встановити курсор на клітинку цільової функції G6. У головному меню вибрати «сервіс», а потім «пошук рішення». З'явиться вікно, в якому потрібно вказати:
1. Цільова комірка - G6;
2. Включити кнопку «максимальне значення»;
3. Вказати змінювані клітинки (розташування змінних) - B8: D8;
4. Записати обмеження. Їх можна записати прямо в цьому ж вікні, але краще вибрати «додати» і у вікні «додати» послідовно записати обмеження:
B8: D8
0 - невід'ємності змінних;
G2: G4
F2: F4 - плановий витрата ресурсів менше їх запасу.
Тепер електронна модель сформована і можна вирішувати задачу. Для цього потрібно повернутися до вікна «пошук рішення» і натиснути «виконати». Якщо електронна модель сформована правильно, то буде отримано повідомлення, що завдання виконане. Результат рішення знаходиться на аркуші EXCEL і в трьох звітах: Результати, Стійкість, Межі.
Рис. 4.1.4
Основні результати видно в таблиці (рис. 4.1.4.). У порівнянні з умовами завдання, показаними на рис. 4.1.3., З'явилися дані:
1. Значення цільової функції в комірці G6 = 15880;
2. Значення змінних в осередках B8: D8: х 1 = 86, х 2 = 0, х 3 = 268; це означає, що 1-й продукт повинен здійснюватися в обсязі 86 одиниць, 2-й - 0, а 3-й - 286 .
3. Плановий витрати ресурсів в осередках G2: G4: витрата 1-го ресурсу = 271,6, витрата 2-го ресурсу = 310, витрати 3-го ресурсу = 2200.
Як видно 1-й ресурс недовикористаний, а 2-й і 3-й витрачені повністю.
Крім результатів в електронній таблиці EXCEL готує три звіту: Результати, Стійкість, Межі. Звіт за результатами зображений на рис 4.1.5, де зображені три таблиці.
Звіт за результатами
Цільова комірка (максимум)
Осередок Ім'я Початково Результат
$ G $ 6 Ціни ЦФ 15880
Змінні Осередки
Обмеження
Рис. 4.1.5
1-а таблиця - цільова осередок - дає значення цільової функції, яка вже є в таблиці EXCEL, значить, ці дані надлишкові.
2-а таблиця - змінні осередку - дає значення змінних, які вже є в таблиці EXCEL, ці дані теж надлишкові.
Третя таблиця - обмеження - дає оцінку обмежень. Колонка «значення» дає значення планового витрати ресурсів і змінних - ці дані є в таблиці EXCEL і тут надлишкові. Стовпець «статус» значенням «пов'язана» відзначає обмеження (не більше або не менше), які в результаті рішення перетворилися в строгі рівності, інші обмеження мають статус «незв'язані». Стовпець «різниця» показує, на яку величину обмеження відхилилися від строгого рівності. Так, наприклад, обмеження 1-го ресурсу 500, планове значення 271,6, різниця = 500 - 271,6 = 228,4.
Звіт по стійкості зображений на рис. 4.1.6. Він складається з двох таблиць.
Звіт по стійкості
Змінні клітинки
Обмеження
Рис. 4.1.6
Таблиця «змінювані осередку» показує значення змінних, які вже є в таблиці EXCEL. Стовпець «нормований градієнт» показує, як впливає збільшення змінних на одиницю на величину цільової функції. Таблиця «обмеження» містить важливу інформацію в стовпці «Лагранжа множники». Ці величини в літературі мають різні назви: об'єктивно обумовлені оцінки (О.О.О.) за Л. Канторовичу, двоїсті оцінки за Д. Данцигу, оптимальні ціни, тіньові ціни та інші. Надалі будемо називати їх найбільш поширеним ім'ям - двоїсті оцінки і позначати - v i, де i - номер обмеження. У даному прикладі v 1 = 0, v 2 = 20,0, v 3 = 4,4. Звіт по межах зображений на рис. 4.1.7.
Звіт по межах
Рис. 4.1.7.
У цьому звіті вже в третій раз дається значення цільової функції 15880, в п'ятий раз значення змінних (х 1 = 86, х 2 = 0, х 3 = 268). Нижня межа для всіх змінних = 0, так, встановлені обмеження по змінним. Верхня межа дорівнює відповідно 86, 0 та 268, так встановлюють обмеження по ресурсах. Цільовий результат показує значення цільової функції при відповідних значеннях змінних. Якщо х 1 = 0, то ЦФ = 10720 і т.д.
Запишемо математичну модель розглянутої задачі в загальному вигляді:
Нехай:
По-бюджет, тобто кількість грошей, яку можна витратити на придбання ресурсів для виробництва продукції, а s i - ринкова ціна i-го ресурсу. Тоді єдине обмеження по ресурсах буде виглядати наступним чином:
.
Сенс цього обмеження - не можна витратити ресурсів на суму більше, ніж В.
Тут:
- Витрата i-го ресурсу в натуральному вираженні в j-му технологічному способу;
- Витрата i-го ресурсу в натуральному вираженні за всіх способів;
- Сумарна ціна i-го ресурсу, витраченого по всіх способів;
- Сумарна ціна всіх ресурсів по всіх технологічних способів.
Вирішимо задачу на максимум продукції з обмеженням по бюджету. За основу візьмемо електронну модель на рис. 4.1.3. і доповнимо цінами ресурсів s i та бюджетом В (рис. 4.1.8)
Рис. 4.1.8
Додаткові величини:
H2: H4 - ціни ресурсів (задаються);
I2: I4 - витрати (обчислюються);
I2 = G2 * H2;
I3: I4 - копіюється з I2;
H6 = 5000 - бюджет (задається);
I6 - витрати всього (обчислюються);
I6 = СУММ (I2: I4).
Обмеження:
B8: D8 0 - невід'ємності змінних;
I6 H6 - сукупні витрати не більше бюджету.
Буде отримано рішення
x 1 = 0; x 2 = 0; x 3 = 409,84.
v = 3,08 - двоїста оцінка обмеження по бюджету - збільшення бюджету на одиницю збільшує валовий продукт на 3,28.
Якщо обмеження по ресурсах в моделі мають сенс і не більше (
) І не менше ( 
), Причому всі величини ( 
) Не негативні, то в загальному випадку висновок про існування чи відсутність допустимого плану зробити не можна. Все залежить від конкретних значень величин і . Можливий випадок, коли для деякого k-го ресурсу встановлено таке обмеження 
, Що воно не може бути виконана через інших обмежень. Тоді немає жодного допустимого плану.
Результатом роботи над курсовим проектом є програма для вирішення завдань лінійного програмування за допомогою двоїстого симплекс-методу.
2. Солодовников А.С., Бабайцев В.А., Браїлів А.В. Математика в економіці. «Фінанси та статистика», 1998 р.
3. Математичне моделювання в задачах. Білолипецький В.М., Шокін Ю.І.
4. Математичне Білолипецький В.М.
Даний підхід до вирішення завдання не призводить до зростання кількості негативних компонент вектора X. Поки не буде отримано Х> 0, процес не припиняється.
Визначаючи оптимальний план двоїстої задачі, знаходимо і оптимальний план вихідної задачі.
Використовуючи при вирішенні, алгоритм двоїстого симплексного методу умова Z j-C j> 0 допускається не враховувати, поки не будуть виключені всі х i <0.
Звичайним симплексним методом визначається оптимальний план. Цей метод зазвичай використовується за умови, що всі х i <0. Щоб перейти до плану вихідної, завдання за одну ітерацію треба визначити q 0j = max (x i / x ij)> 0.
Завдання лінійного програмування можна вирішувати двоїстим симплексним методом. Системи обмежень в задачах при позитивному базисі мають вільні члени будь-якого знаку. Двоїстий симплексний метод дозволяє значно зменшити розміри симплексного таблиці та кількість перетворень системи обмежень.
2. Розробка програми
2.1 Постановка завдання
Необхідно спланувати роботу швейної майстерні на деякий період. Встановлено перелік продукції, що випускається, відома ринкова ціна кожного продукту. Для виробництва продукції використовуються ресурси: матеріал, нитки, гудзики, праця закрійників, швачок-моторісток і т.д. Встановлено повний перелік цих ресурсів і загальна кількість кожного ресурсу, яке може бути витрачено в плановому періоді. Відомий витрата кожного ресурсу на одиницю кожного продукту. Необхідно визначити, скільки кожної продукції потрібно робити, щоб сумарна ринкова ціна всієї продукції (випуск, виручка) була найбільшою.
Введемо наступні позначення:
i = 1, ..., m - номери (індекси) використовуваних ресурсів;
j = 1, ..., n - номери (індекси) продуктів;
Рис. 2
Кожен рядок матриці відповідає одного ресурсу, кожен стовпець - одному продукту. Праворуч від кожного рядка записана величина обмеження по ресурсу (b 1, ..., b i, ..., b m); внизу кожного стовпця - ціна продуктів (з 1, ..., с j, ..., с m).
У кожній клітинці матриці записані так звані технологічні коефіцієнти a ij, показують витрата i-го ресурсу на виробництво одиниці j-го продукту.
Запишемо конкретний числовий приклад
Рис. 3
2.2 Побудова математичної моделі
Тепер приступимо до створення математичної моделі, тобто до математичного запису завдання.
Цільова функція:
Обмеження:
x 1 ³ 0;
x 2 ³ 0;
x 3 ³ 0.
2.3 Опис рішення даного завдання
Вирішимо поставлену вище задачу із застосуванням EXCEL.
Зміст осередків:
B1: D1 - імена продуктів (технологічних способів);
A2: A4 - імена ресурсів;
B2: D4 - технологічні коефіцієнти (витрати ресурсів при поодиноких интенсивностях технологічних способів);
B6: D6 - ціни продуктів;
B8: D8 - змінні;
F2: F4 - запас ресурсів;
G2: G4 - планові витрати ресурсів, виходять в результаті рішення;
G6 - значення цільової функції, виходить в результаті рішення.
Формули для обчислень:
G2 = СУММПРОІЗВ (B $ 8: D $ 8; B2: D2);
G3: G4 - копіюються з G2;
G6 = СУММПРОІЗВ (B8: D8; B6: D6).
Запишемо формули в комірки G2: G4. Встановити курсор на G2. На панелі інструментів вибрати значок формул (f). З'являться два вікна. У вікні «категорія» вибрати «математичні», потім у вікні «функція» вибрати «СУММПРОІЗВ». З'явиться вікно «СУММПРОІЗВ». У ньому потрібно вказати, де розташовуються операнди. Перший операнд - рядок B $ 8: D $ 8, другий операнд - стоку B2: D2. У комірки G3: G4 формулу скопіювати з G2. Аналогічним чином записати формулу цільової функції в клітинку G6. Тепер потрібно вказати інші умови розв'язання задачі. Встановити курсор на клітинку цільової функції G6. У головному меню вибрати «сервіс», а потім «пошук рішення». З'явиться вікно, в якому потрібно вказати:
1. Цільова комірка - G6;
2. Включити кнопку «максимальне значення»;
3. Вказати змінювані клітинки (розташування змінних) - B8: D8;
4. Записати обмеження. Їх можна записати прямо в цьому ж вікні, але краще вибрати «додати» і у вікні «додати» послідовно записати обмеження:
B8: D8
G2: G4
Тепер електронна модель сформована і можна вирішувати задачу. Для цього потрібно повернутися до вікна «пошук рішення» і натиснути «виконати». Якщо електронна модель сформована правильно, то буде отримано повідомлення, що завдання виконане. Результат рішення знаходиться на аркуші EXCEL і в трьох звітах: Результати, Стійкість, Межі.
Рис. 4.1.4
Основні результати видно в таблиці (рис. 4.1.4.). У порівнянні з умовами завдання, показаними на рис. 4.1.3., З'явилися дані:
1. Значення цільової функції в комірці G6 = 15880;
2. Значення змінних в осередках B8: D8: х 1 = 86, х 2 = 0, х 3 = 268; це означає, що 1-й продукт повинен здійснюватися в обсязі 86 одиниць, 2-й - 0, а 3-й - 286 .
3. Плановий витрати ресурсів в осередках G2: G4: витрата 1-го ресурсу = 271,6, витрата 2-го ресурсу = 310, витрати 3-го ресурсу = 2200.
Як видно 1-й ресурс недовикористаний, а 2-й і 3-й витрачені повністю.
Крім результатів в електронній таблиці EXCEL готує три звіту: Результати, Стійкість, Межі. Звіт за результатами зображений на рис 4.1.5, де зображені три таблиці.
Звіт за результатами
Цільова комірка (максимум)
Осередок Ім'я Початково Результат
$ G $ 6 Ціни ЦФ 15880
Змінні Осередки
| Осередок Ім'я Початково Результат |
| $ B $ 8 Перем Пр1 0 86 |
| $ C $ 8 Перем Пр2 0 0 |
| $ D $ 8 Перем Пр3 0268 |
| Осередок Ім'я Значення Формула Статус Різниця |
| $ G $ 2 Рес 1 Витрата 271,6 $ G $ 2 |
| $ G $ 3 Рес 2 Витрата 310 $ G $ 3 |
| $ G $ 4 Рес 3 Витрата 2200 $ G $ 4 |
| $ B $ 8 Перем Пр1 86 $ B $ 8 |
| $ C $ 8 Перем Пр2 0 $ C $ 8 |
| $ D $ 8 Перем Пр3 268 $ D $ 8 |
1-а таблиця - цільова осередок - дає значення цільової функції, яка вже є в таблиці EXCEL, значить, ці дані надлишкові.
2-а таблиця - змінні осередку - дає значення змінних, які вже є в таблиці EXCEL, ці дані теж надлишкові.
Третя таблиця - обмеження - дає оцінку обмежень. Колонка «значення» дає значення планового витрати ресурсів і змінних - ці дані є в таблиці EXCEL і тут надлишкові. Стовпець «статус» значенням «пов'язана» відзначає обмеження (не більше або не менше), які в результаті рішення перетворилися в строгі рівності, інші обмеження мають статус «незв'язані». Стовпець «різниця» показує, на яку величину обмеження відхилилися від строгого рівності. Так, наприклад, обмеження 1-го ресурсу 500, планове значення 271,6, різниця = 500 - 271,6 = 228,4.
Звіт по стійкості зображений на рис. 4.1.6. Він складається з двох таблиць.
Звіт по стійкості
Змінні клітинки
| Осередок Ім'я Результат Норір. Значення градієнт |
| $ B $ 8 Перем Пр1 86 0 |
| $ C $ 8 Перем Пр2 0 -22,8 |
| $ D $ 8 Перем Пр3 268 0 |
| Осередок Ім'я Результат. Лагранжа значення Множник |
| $ G $ 2 Рес 1 Витрата 271,6 0 |
| $ G $ 3 Рес 2 Витрата 310 1920 |
| $ G $ 4 Рес 3 Витрата 2200 4,4 |
Таблиця «змінювані осередку» показує значення змінних, які вже є в таблиці EXCEL. Стовпець «нормований градієнт» показує, як впливає збільшення змінних на одиницю на величину цільової функції. Таблиця «обмеження» містить важливу інформацію в стовпці «Лагранжа множники». Ці величини в літературі мають різні назви: об'єктивно обумовлені оцінки (О.О.О.) за Л. Канторовичу, двоїсті оцінки за Д. Данцигу, оптимальні ціни, тіньові ціни та інші. Надалі будемо називати їх найбільш поширеним ім'ям - двоїсті оцінки і позначати - v i, де i - номер обмеження. У даному прикладі v 1 = 0, v 2 = 20,0, v 3 = 4,4. Звіт по межах зображений на рис. 4.1.7.
Звіт по межах
| Осередок Цільове Значення ім'я |
| $ G $ 6 Ціни ЦФ 15880 |
| Осередок Змінне Значення ім'я | Нижній Цільовий межа результат | Нижній Цільовий межа результат |
| $ B $ 8 Перем Пр1 86 | 0 10720 | 86 15880 |
| $ C $ 8 Перем Пр2 0 | 0 15880 | 0 15880 |
| $ D $ 8 Перем Пр3 268 | 0 5160 | 268 15880 |
У цьому звіті вже в третій раз дається значення цільової функції 15880, в п'ятий раз значення змінних (х 1 = 86, х 2 = 0, х 3 = 268). Нижня межа для всіх змінних = 0, так, встановлені обмеження по змінним. Верхня межа дорівнює відповідно 86, 0 та 268, так встановлюють обмеження по ресурсах. Цільовий результат показує значення цільової функції при відповідних значеннях змінних. Якщо х 1 = 0, то ЦФ = 10720 і т.д.
Запишемо математичну модель розглянутої задачі в загальному вигляді:
Нехай:
По-бюджет, тобто кількість грошей, яку можна витратити на придбання ресурсів для виробництва продукції, а s i - ринкова ціна i-го ресурсу. Тоді єдине обмеження по ресурсах буде виглядати наступним чином:
Сенс цього обмеження - не можна витратити ресурсів на суму більше, ніж В.
Тут:
Вирішимо задачу на максимум продукції з обмеженням по бюджету. За основу візьмемо електронну модель на рис. 4.1.3. і доповнимо цінами ресурсів s i та бюджетом В (рис. 4.1.8)
Рис. 4.1.8
Додаткові величини:
H2: H4 - ціни ресурсів (задаються);
I2: I4 - витрати (обчислюються);
I2 = G2 * H2;
I3: I4 - копіюється з I2;
H6 = 5000 - бюджет (задається);
I6 - витрати всього (обчислюються);
I6 = СУММ (I2: I4).
Обмеження:
B8: D8
I6
Буде отримано рішення
x 1 = 0; x 2 = 0; x 3 = 409,84.
v = 3,08 - двоїста оцінка обмеження по бюджету - збільшення бюджету на одиницю збільшує валовий продукт на 3,28.
Якщо обмеження по ресурсах в моделі мають сенс і не більше (
Висновок
У результаті проведеної роботи було розглянуто теоретичний матеріал, присвячений вирішенню двоїстих задач лінійного програмування, і процес їх вирішення був автоматизований, з допомогою програми MS Excel.Результатом роботи над курсовим проектом є програма для вирішення завдань лінійного програмування за допомогою двоїстого симплекс-методу.
Список використаної літератури
1. Кузнєцов Ю.М., Кузубов В.І., Волощенко А.Б. Математичне програмування. «Наука», 1980 р.2. Солодовников А.С., Бабайцев В.А., Браїлів А.В. Математика в економіці. «Фінанси та статистика», 1998 р.
3. Математичне моделювання в задачах. Білолипецький В.М., Шокін Ю.І.
4. Математичне Білолипецький В.М.