• Теорема подвійності
  • 1.2.2 Симетричні двоїсті задачі
  • 1.4 Двоїстий симплексний метод
  • Список використаної літератури


  • Дата конвертації24.03.2017
    Розмір35.91 Kb.
    Типкурсова робота

    Скачати 35.91 Kb.

    Двоїстість в лінійному програмуванні

    Вступ

    Під двоїстої завданням розуміється допоміжна задача лінійного програмування, що формулюється за допомогою певних правил безпосередньо з умов прямої задачі. Зацікавленість у визначенні оптимального розв'язання прямої задачі шляхом вирішення двоїстої до неї завдання обумовлена ​​тим, що обчислення при вирішенні ДЗ можуть виявитися менш складними. Трудомісткість обчислень при вирішенні ЗЛП більшою мірою залежить від числа обмежень, а не від кількості змінних.

    Метою курсового проекту є вивчити літературу з обраної теми і навчитися застосовувати на практиці симплекс - метод для вирішення прямої і двоїстої задачі лінійного програмування, а також вирішити двоїсту задачу лінійного програмування за допомогою програми MSExcel.

    Курсовий проект складається з вступу, двох розділів і висновку.

    У першому розділі розглядаються основні поняття і пропозиції теорії подвійності ЗЛП, види математичних моделей двоїстих задач і їх економічна інтерпретація.

    У другому розділі розглядається рішення двоїстої завдання за допомогою програми MSExcel.

    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 + 2y 2 + 5y 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> 0Y> 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

    Змінні Осередки

    Осередок Ім'я Початково Результат
    $ B $ 8 Перем Пр1 0 86
    $ C $ 8 Перем Пр2 0 0
    $ D $ 8 Перем Пр3 0 268

    обмеження

    Осередок Ім'я Значення Формула Статус Різниця
    $ G $ 2 Рес 1 Витрата 271,6 $ G $ 2 $ F $ 2 не пов'язаний 228,4
    $ G $ 3 Рес 2 Витрата 310 $ G $ 3 $ F $ 3 пов'язане 0
    $ G $ 4 Рес 3 Витрата 2200 $ G $ 4 $ F $ 4 пов'язане 0
    $ B $ 8 Перем Пр1 86 $ B $ 8 0 не пов'язаний 86
    $ C $ 8 Перем Пр2 0 $ C $ 8 0 пов'язане 0
    $ D $ 8 Перем Пр3 268 $ D $ 8 0 не пов'язаний 268

    Мал. 4.1.5

    1-я таблиця - цільова осередок - дає значення цільової функції, яка вже є в таблиці EXCEL, значить, ці дані надлишкові.

    2-я таблиця - змінювані комірки - дає значення змінних, які вже є в таблиці EXCEL, ці дані теж надлишкові.

    3-тя таблиця - обмеження - дає оцінку обмежень. Колонка «значення» дає значення планового витрати ресурсів і змінних - ці дані є в таблиці 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 20
    $ G $ 4 Рес 3 Витрата 2200 4,4

    Мал. 4.1.6

    Таблиця «змінювані комірки» показує значення змінних, які вже є в таблиці 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

    Мал. 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 -го ресурсу встановлено таке обмеження , Що воно не може бути виконано через інших обмежень. Тоді немає жодного допустимого плану.


    висновок

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

    Результатом роботи над курсовим проектом є програма для вирішення завдань лінійного програмування за допомогою двоїстого симплекс-методу.


    Список використаної літератури

    1. Кузнецов Ю.М., Кузубов В.І., Волощенко А.Б. Математичне програмування. «Наука», 1980 г.

    2. Солодовников А.С., Бабайцев В.А., Браїлів А.В. Математика в економіці. «Фінанси і статистика», 1998 р

    3. Математичне моделювання в задачах. Белолипецкий В.М., Шокін Ю.І.

    4. Математичне Белолипецкий В.М.