20. Приклад практичного використання двоїстих оцінок у аналізі економічної задачі

Фірма виготовляє продукцію трьох видів: А, В і С. Потрібний певний час для обробки одиниці кожного виду продукції на різному обладнанні.

Тип обладнання Тривалість обробки одиниці продукції виду Тривалість роботи обладнання на місяць

А В С

І 1 2 4 360

ІІ 2 4 2 520

ІІІ 1 1 2 220

Ціна одиниці продукції видів А, В і С дорівнює 90 дол., 110 дол. та 150 дол. відповідно. Визначити, яку продукцію і в якому обсязі слід виготовляти, щоб фірма отримувала найбільший дохід.

Розв’язавши цю задачу симплекс-методом, отримаємо таку останню симплексну таблицю:

Керівництво фірми цікавить відповідь на таке запитання: «Чи зміниться оптимальний план виробництва продукції і якщо зміниться, то яким буде новий оптимальний план у кожній з наведених нижче ситуацій?»

1. Фірма може збільшити тривалість роботи обладнання типів 2 та 3 відповідно на 100 і 80 год на місяць, орендуючи для цього додаткове обладнання, але орендна плата становитиме 5000 дол. Чи вигідно це? Якщо вигідно, то яким має бути новий оптимальний план виробництва продукції?

2. Фінансовий відділ фірми вважає, що загострення конкуренції на ринку збуту може призвести до зниження ціни на продукцію В на 25 дол. Як це позначиться на оптимальному плані виробництва продукції фірми?

3. Відділ досліджень і розробок фірми пропонує виготовляти дешевшу модифікацію продукції С. Тривалість обробки одиниці цієї нової продукції на обладнанні типів 1, 2 та 3 становить відповідно 4, 3 і 1 год. Орієнтовна ціна одиниці нової продукції дорівнює 120 дол. Керівництво фірми цікавить, чи буде за таких умов виробництво нової продукції вигідним.

4. Споживач продукції виду А за певних обставин порушив попередню домовленість і відмовився прийняти більш як 100 од. продукції. Визначити, як слід змінити план виробництва своєї продукції, щоб уникнути втрат, пов’язаних із надвиробництвом цього виду продукції.

Розв’язання. Із наведеної в умові задачі симплекс-таблиці маємо: Х* = (180; 40; 0; 100; 0; 0), max F = 20 600, Y* = (0; 10; 70). Оптимальним планом виробництва продукції на фірмі є випуск 180 од. продукції виду А та 40 од. продукції виду В. Виготовлення продукції виду С не передбачається. При цьому фірма отримає максимальну виручку обсягом 20 600 дол. на місяць.

1. Збільшення тривалості роботи обладнання дасть змогу збільшити випуск продукції, тобто змінити оптимальний план і дохід фірми. Оскільки Db1 = 0, Db2 = 100, Db3 = 80, то новий оптимальний план визначається так:

2. Новий план допустимий (всі хj 0), і тому оптимальні значення двоїстих оцінок зберігаються: Y* = (0; 10; 70). Приріст доходу фірми в результаті зміни оптимального плану виробництва продукції розраховується так:

max DZ = Db1y1 + Db2y2 + Db3y3 = = 100 • 10 + 80 • 70 = 6600 дол.

Оскільки дохід фірми від додаткового використання обладнання груп 2 і 3 перевищує витрати на його оренду (6600 > 5000), то природно, що така тактика фірми буде вигідною. При цьому оптимальним планом виробництва стане випуск 290 од. продукції виду А і 10 од. продукції виду В. Невикористаний час роботи обладнання типу І зменшиться до 50 год на місяць, а дохід фірми за відрахуванням витрат на оренду обладнання дорівнюватиме 20 600 + (6600 – 5000) = 22 200 дол. на місяць.

2. Зниження ціни одиниці продукції В на Dc2 (–25 дол.) стосується всього оцінкового рядка симплекс-таблиці, оскільки х2 є базисною змінною. Нові Fj – cj матимуть такі значення:

F3 – c3 = 10 – 1Dc2 = 10 + 25 = 35;

F5 – c5 = 10 + 1/2Dc2 = 10 – 12,5 = –2,5;

F6 – c6 = 70 – 1Dc2 = 70 + 25 = 95.

Якби всі здобуті оцінки задовольняли умову Zj – Cj 0, то це означало б, що попри зниження ціни план виробництва продукції на фірмі не зміниться. Але оцінка F5 – c5 не задовольняє умову оптимальності задачі на максимум, і тому можна висновувати, що істотне зниження ціни одиниці продукції виду В порушує визначений раніше оптимальний план виробництва продукції, оскільки випуск цієї продукції стає для фірми невигідним, нерентабельним.

Новий оптимальний план визначається у процесі подальшого розв’язання задачі симплекс-методом:

Отже, у розглянутій ситуації зниження ціни одиниці продукції виду В на 25 дол. різко змінить структуру та обсяги виробництва продукції на фірмі. Вигідним стане випуск лише продукції виду А обсягом 220 од.: при цьому можливий час роботи обладнання типів 1 та 2 використовуватиметься не повністю. Усе це призведе до зменшення виручки фірми до 19 800 дол. на місяць.

3. Обсяг виробництва нової продукції в оптимальному плані позначимо через х7. Тоді математична модель прямої задачі матиме такий вигляд:

У математичній моделі двоїстої задачі змінній х7 відповідатиме таке обмеження:

Оцінимо рентабельність виробництва нової продукції за допомогою двоїстих оцінок: 4 • 0 + 3 • 10 + 1 • 70 = 100, що є меншим за 120. Отже, загальна вартість усіх ресурсів, що витрачаються на випуск одиниці нової продукції, не перевищує орієнтовної ціни цієї продукції, і тому її виробництво для фірми є вигідним, рентабельним. Завдяки цьому визначений раніше оптимальний план виробництва продукції можна поліпшити за рахунок уведення в нього х7.

Для цього за допомогою оберненої матриці необхідно визначити елементи стовпчика «х7» останньої симплекс-таблиці:

Результати однієї ітерації симплекс-методу, що приводить до нового оптимального плану задачі, наведено нижче.

Отже, оптимальним планом є Х* = (160; 20; 0; 0; 0; 0; 40), а max Z = 21 400. Керівництво фірми має підтримати пропозицію відділу досліджень та розробок і налагодити виробництво нової продукції, яка є рентабельною. Виготовляючи її обсягом 40 од., а також продукцію видів А та В обсягом 160 і 20 од. відповідно, фірма зможе збільшити обсяг виручки до 21 400 дол. на місяць згідно з новим оптимальним планом виробництва продукції.

4. Четверта запропонована ситуація математично пов’язана із введенням в умову задачі додаткового обмеження, що може привести до таких наслідків:

а) нове обмеження для визначеного оптимального плану виконується. Тоді воно є надлишковим, зайвим і його включення до моделі не змінює визначеного плану;

б) нове обмеження для визначеного оптимального плану не виконується, і тоді за допомогою двоїстого симплекс-методу необхідно знайти новий оптимальний план.

За умовою задачі додатковим є обмеження х1 < 100. Але воно суперечить оптимальному обсягу продукції виду А, що дорівнює 180 од. Тому необхідно приєднати це додаткове обмеження до симплекс-таблиці та продовжити розв’язання задачі, але вже за допомогою двоїстого симплекс-методу. Для цього спочатку зведемо додаткове обмеження до канонічного вигляду: х1 + х7 = 100.

Оскільки в оптимальному плані змінна х1 є базисною, то її необхідно записати через небазисні невідомі. Це робиться так. У симплекс-таблиці, яку наведено в умові задачі, рядок змінної «х1» подається рівнянням:

1 • х1 + 0 • х2 + 3 • х3 + 0 • х4 – 1/2 • х5 + 2 • х6 = 180.

З нього запишемо вираз для х1:х1 = 180 – 3х3 + 1/2х5 – 2х6.

Підставивши цей вираз в додаткове обмеження, отримаємо:

180 – 3х3 + 1/2х5 – 2х6 + х7 = 100

aбо – 3х3 + 1/2х5 – 2х6 + х7 = – 80.

Застосування двоїстого симплекс-методу приведе до нового оптимального плану задачі.

В останній таблиці маємо: Х* = (100; 200/3; 80/3; 20; 0;0), а max Z = 61 000/3 » 20 333.

Проаналізуємо цей план. Прийнявши до уваги ситуацію, що склалася, керівництво фірми змушене змінити структуру виробництва продукції. Тепер з урахуванням вимог споживача фірма виготовлятиме 100 од. продукції виду А, 200/3 од. продукції виду В і 80/3 од. продукції виду С. У результаті такого плану випуску продукції виручка фірми дещо зменшиться (до 20 333 дол. на місяць).

22. Постановка Т-задачи. Свойства транспортной задачи. Нахождение начальных опорных планов

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Постановка Т-задачи. Пусть в пунктах А1, ... , Am производят некоторый однородный продукт, причем объем производства в пункте Ai составляет ai единиц, i = 1,...,m. Допустим, что данный продукт потребляют в пунктах B1, … , Bn, a объем потребления в пункте Вj составляет bj одиниць j = 1,…,n.Предположим , что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные издержки по перевозке единицы продукции из пункта Ai в пункт Вj равны cij (i = 1,…,m; j = 1,…,n ). Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей Вj полностьюудовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.

Свойства транспортной задачи

1. Для разрешимости Т-задачи необходимо и достаточно, чтобы вяполнялось условие баланса

то есть, чтобы суммарный объем производства равнялся объему потребления.

2. Ранг системы ограничений равен

Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.

Нахождение начальных опорных планов

Существует несколько методов построения начальных опорных планов Т-задачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента.

Метод северо-западного угла. Основную идею метода рассмотрим на конкретном примере.

Пусть дана Т-задача с четырьмя пунктами производства А1, А2, А3, А4 с объемами производства и пунктами потребления с объемами потребления соответственно .

Построим матрицу Х размером 4х4, причем для удобства вычислений снизу от нее оставим строку bj, справа столбец ai. Кроме того, снизу от bj образуем строки , где будем записывать неудовлетворенные потребности, а справа от ai- столбцы , где будем записывать остатки невывезенного продукта .

Заполнение таблицы начинают с левого верхнего элемента таблицы X - x11, что и обусловило название метода. Сравнив с и выбрав меньшее из них, получим x11=1. Записываем это значение в матрицу Х0. Так как первый выбор произведен по строке, то остальная часть первой строки должна быть заполнена нулями. Во вспомогательном столбце записываем остатки невывезенного продукта, , а в строке - неудовлетворенные потребности после одного шага заполнения.

Переходим к второй строке и начинаем заполнение с элемента (новый северо-западный угол незаполненной части таблицы). Сравнивая выбираем меньшее из них, и потому . Остальную часть второй строки заполняем нулями. Далее заполняем таблицу аналогично. После окончания процесса заполнения будем иметь начальный план Х0. Полученный план является базисным (опорным), так как из его ненулевых элементов нельзя составить цикл. Кроме того, он удовлетворяет условиям задачи, так как

Формальное описание алгоритма. I. Определяют верхний левый элемент матрицы Х:

Возможные три случая: а) если то и всю первую строку, начиная со второго элемента, заполняют нулями; б) если , то , а все оставшиеся элементы первого столбца заполняют нулями; в) если

• то и все оставшиеся элементы первых столбцов и строки заполняют нулями.

Находим

на этом один шаг метода заканчивается.

2. Пусть уже проделано k шагов. (k+1)-й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент

причем

, (3.1.27)

где (3.1.28)

Если , то заполняем нулями строку , начиная с ( +1)-го элемента. В противном случае заполняем нулями столбец , начиная с элемента ( +1). Если , то заполняем нулями остаток строки и столбца . Далее вычисляем . На этом (k+1)-й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.

Метод минимального элемента.

Этот метод является вариантом метода северо-западного угла, учитывающим специфику матрицы транспортных затрат С= . В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план, сокращая общее количество итераций по его дальнейшей оптимизации.

Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х0.

Пусть элементом с минимальным порядковым номером оказался . Возможные три случая: а) если , то оставшуюся часть -й строки заполняем нулями; б) если , то оставшуюся часть -го столбца заполняем нулями; в) если , то оставшуюся часть -й строки и -го столбца заполняем нулями.

Дале этот процесс повторяют с незаполненной частью матрицы Х1