Поиск по базе сайта:
Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування» icon

Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування»




НазваМетодичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування»
Сторінка7/8
Дата конвертації02.08.2013
Розмір1.22 Mb.
ТипМетодичні вказівки
1   2   3   4   5   6   7   8

^ Правила складання двоїстих задач:

У всіх обмеженнях початкової задачі вільні члени повинні знаходитись у правій частині, а невідомі – у лівій.

Обмеження нерівностей початкової задачі повинні бути записані таким чином, щоб знаки нерівностей у них були спрямовані в один бік.

Характер цільової функції однієї з задач двоїстої пари змінюється на протилежний: цільова функція вихідної задачі формулюється на максимум, а цільова функція двоїстої задачі – на мінімум, при цьому в задачі на максимум всі нерівності в функціональних обмеженнях мають вид ≤, а в задачі на мінімум – вид ≥.

Кожному обмеженню початкової задачі відповідає невідоме в двоїстій задачі, при цьому невідоме, яке відповідає обмеженню у вигляді нерівності, повинне задовольняти умові невід’ємності, а невідоме, яке відповідає обмеженню рівності, може бути довільного знаку. Дані відношення справедливі для обмежень двоїстої моделі і змінних вихідної, тобто умові невід’ємності змінної вихідної задачі буде відповідати обмеження у формі нерівності двоїстої задачі, а умові довільної за знаком змінної xj – обмеження в формі рівності.

Коефіцієнти при змінних в цільовій функції вихідної (двоїстої) задачі є вільними членами обмежень двоїстої (вихідної) задачі.

Матриці обмежень вихідної та двоїстої задач є взаємотранспонованими. Тобто, рядок коефіцієнтів при змінних yi j-го обмеження двоїстої задачі є стовпчиком коефіцієнтів при xj в обмеженнях вихідної задачі.


Приклад

На підставі інформації, наведеної в таблиці, скласти план виробництва, що максимізує обсяг прибутку та провести аналіз чутливості розв’язків до змін вхідної моделі.


Ресурси

Витрати ресурсів

на одиницю продукції

Наявність

ресурсів

А

Б

Праця

2

4

2000

Сировина

4

1

1400

Устаткування

2

1

800

Прибуток на одиницю продукції

40

60





Розв’язання

Економіко-математична модель прямої задачі буде мати вигляд:






Економіко-математична модель двоїстої задачі буде мати вигляд:





.


У результаті розв'язання прямої задачі симплексним методом був отриманий наступний оптимальний план:


X = (200; 400; 0; 200; 0),






Y = (40/3; 0; 20/3),






Після того, як оптимальний розв’язок отриманий, можна провести дослідження його чутливості до певних змін вихідної моделі. У задачі, що розглядається, наприклад, може викликати інтерес те, як вплине на оптимальний розв’язок зміна запасів сировини й зміна прибутку від одиниці продукції. У зв'язку з цим логічно з'ясувати:

  1. Збільшення обсягів якого виду ресурсів є найбільш вигідним?

  2. На скільки можна збільшити запас сировини для поліпшення отриманого оптимального значення цільової функції?

  3. Яким є діапазон зміни того або іншого коефіцієнта цільової функції, за якого не відбувається зміни оптимального розв’язку?

Для відповіді на ці питання необхідно визначити:

  1. ^ Цінність ресурсів

У прикладі об'єктивно обумовлені оцінки ресурсу «праця» дорівнюють 40/3 (y1 = 40/3); «сировина» — 0 (y2=0); «устаткування» — 20/3 (y3= 20/3). Дефіцитний ресурс, що повністю використовується в оптимальному плані має позитивну оцінку; недефіцитний, використовується не повністю, має нульову оцінку. У прикладі «сировина» не є дефіцитним ресурсом:


а «праця» і «устаткування» — дефіцитні ресурси:


Чим вищою є величина оцінки yi, тим гостріша дефіцитність i-гo ресурсу.

У прикладі «праця» є більш дефіцитною, ніж «устаткування»: 40/3>20/3. Найбільш вигідним є збільшення обсягів ресурсу «праця».

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

^ 2 Чутливість розв’язку до зміни запасів сировини

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

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

Модель вихідної задачі лінійного програмування у матричній формі має вигляд


,

А*Х≤В,

X≥0,

де X = (x1, x2,…, xn)вектор невідомих;

C = (c1, c2,…, cn) вектор коефіцієнтів при невідомих у цільовій функції;

В = (b1, b2,…, bm) вектор вільних членів обмежень вихідної задачі;


А = матриця коефіцієнтів у системі обмежень.


Для приведення задачі до канонічної форми необхідно увести m додаткових змінних. Задача набуде вигляду


,

А*Х=В,

X≥0,

де вектор невідомих змінних X буде тепер мати розмірність n+m. Розмірність матриці А також зміниться і буде дорівнювати m×(n+m).

Нехай відомий оптимальний план. Вектор X можна розбити на два підвектори: X*>0 та Х° = 0. До першого включені невідомі, що ввійшли до базису оптимального розв’язку (тобто ненульові в оптимальному плані). Відповідно матрицю А можна розбити на дві підматриці: А* (розмірність т×т) і А0 (розмірність т×п). Першу з них сформують ті стовпчики матриці А, які відповідають ненульовим невідомим в оптимальному плані. А*-1 матриця, обернена до матриці А* (А*-1×А* = Е, де Е одинична матриця). А*-1 позначається через D, тоді X* = DB.

Матриця D характеризує вплив ресурсів на величину випуску продукції X.

Із урахуванням X = DB можна записати наступне

ΔX = DΔB.

Дане співвідношення визначає величину структурних зрушень у випуску продукції при зміні обмежень вихідної задачі. Зі співвідношень другої теореми двоїстості відомо, що двоїсті оцінки (змінні двоїстої задачі) тісно пов'язані з оптимальним планом простої задачі. Будь-яка зміна вихідних даних прямої задачі може вплинути як на її оптимальний план (ΔX = DΔB), так і на систему оптимальних двоїстих оцінок. Тому, щоб проводити економічний аналіз із використанням двоїстих оцінок, потрібно знати їхній інтервал стійкості.

Друга властивість двоїстих оцінок означає, що зміна значень величини bi приведе до збільшення або зменшення . Ця зміна, як було відзначено раніше, визначається величиною yi і може бути визначена лише тоді, коли у випадку зміни величин bi значення змінних yi в оптимальному плані відповідної двоїстої задачі залишаються незмінними. Тому необхідно визначити такі інтервали зміни кожного з вільних членів системи лінійних рівнянь АХ=В, у яких оптимальний план двоїстої задачі не змінюється. Це має місце тоді, коли серед компонентів вектора X=DB немає від’ємних.

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

Межі зменшення (нижня границя) визначаються за тими xk (k = 1,..., m), для яких відповідні dki >0:

(1)

Межі збільшення (верхня границя) визначаються за тими xk (k = 1,..., m), для яких відповідні dki <0:

(2)

Послаблення будь-якого і-го обмеження приводить до того, що з певного моменту виявляється можливим змінити структуру (набір векторів) у базисі плану, що веде до стрибкоподібного зменшення величини оцінки. Так триває доти, доки і--й ресурс взагалі перестане бути дефіцитним і його оцінка перетвориться на нуль.

Інтервали стійкості двоїстих оцінок у прикладі, що розглядається можна обчислити таким чином. Матриця ^ А має вигляд:


Після приведення задачі до канонічної форми матриця А набуде наступного вигляду:


Із ненульовими значеннями до оптимального плану ввійшли: х1* = 200, х2* = 400 і х4* = 200, отже, матриця А* буде складена з першого, другого й четвертого стовпчиків матриці А:


Для обчислення інтервалів стійкості необхідно знайти матрицю D = А*-1:


Для обчислення інтервалів стійкості за формулами (1) і (2) приймається, що х1* = 200 = xk=1, х2* = 400 = xk=2 і х4* = 200 = xk=3.

Інтервали стійкості першого ресурсу — «праця»:


.


При зміні запасів ресурсу «праця» у межах від 1400 до 3200 одиниць двоїста оцінка його не зміниться.

Інтервали стійкості другого ресурсу - «сировина»: цей ресурс в оптимальному плані використовується не повністю, тому не має верхньої границі інтервалів стійкості; нижня границя визначається таким чином:


Інтервали стійкості третього ресурсу — «устаткування»:


3. Чутливість розв’язку до зміни коефіцієнтів цільової функції

Так як будь-які зміни коефіцієнтів цільової функції впливають на оптимальність отриманого раніше розв’язку, то необхідно знайти такі діапазони зміни коефіцієнтів у цільовій функції (розглядаючи кожний з коефіцієнтів окремо), за яких оптимальні значення змінних залишаються постійними. Припустимі діапазони зміни коефіцієнтів у цільовій функції визначаються зі співвідношень:


Використовуючи ці співвідношення в розглянутій задачі, можна обчислити для першого коефіцієнта цільової функції:




для другого коефіцієнта:


Таким чином, знайдений оптимальний план випуску продукції не буде змінюватися у випадку зміни прибутку на одиницю продукції А в діапазоні від 30 до 120 і прибутку на одиницю продукції Б у діапазоні від 20 до 80.


^ Завдання до лабораторної роботи

Скласти математичні моделі прямої та двоїстої задачі, визначити оптимальні плани задач, провести економічний аналіз отриманих розв’язків.


Завдання 1 Фірма “Коваленко і К” виробляє двері двох типів — “Класика” і “Модерн” і продає їх у будівельних магазинах. Двері “Класика” коштують півтори тисячі гривень, а “Модерн” – дві тисячі гривень. Попит на продукцію фірми практично необмежений. На виробництві дверей в компанії зайнято 8 робочих, які можуть працювати не більше 40 годин на тиждень з оплатою 20 грн за годину. Для виробництва дверей потрібне дерево і скло. Протягом тижня фірма може купити 600 м2 дерева за ціною 22 грн за 1 м2 і 300 м2 скла за ціною 80 грн за 1 м2. Для виробництва одних дверей “Класика” потрібно 2 м2 дерева і 0,5 м2 скла, а для виробництва одних дверей “Модерн” необхідно 1,5 м2 дерева і 1 м2 скла. На виробництво (обробка і збирання) одних дверей, незалежно від типу, робочий витрачає 1 годину. Керівництво хотіло б знати: як можна оптимізувати роботу компанії?

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


Завдання 2 У цеху з виробництва іграшок випускають два види колекційних моделей: солдатики і автомобілі. Кожен солдатик продається за 27 грн і для свого виробництва вимагає витратних матеріалів на 10 грн, збільшуючи при цьому витрати фірми (податки, накладні витрати, зарплата) на 14 грн.

Автомобіль продається за 21 грн і для свого виробництва вимагає витратних матеріалів на 9 грн, збільшуючи, в свою чергу, витрати фірми (податки, накладні витрати, зарплата) на 10 грн.

У процесі виробництва таких іграшок виконуються дві технологічні операції: збирання і фарбування. Для виробництва одного солдатика необхідно затратити 2 години на фарбування і 1 годину на збирання, для виробництва одного автомобіля – 1 годину на фарбування і 1 годину на збирання.

Зараз фірма не відчуває нестачі у витратних матеріалах, але на збирання протягом тижня може бути виділено лише 80 годин, а на фарбування –
100 годин, що пов’язано з виробничими обмеженнями. Відділ маркетингу стверджує, що автомобілі розкуповуються в необмеженій кількості, а солдатиків продається не більше 40 штук на тиждень.

Необхідно визначити, яким чином фірма може збільшити свій щотижневий дохід.


Завдання 3 Компанія «Промрозчин» випускає 2 типи промислових розчинів: С1 і С2. Завод, що виробляє розчини, працює 40 годин на тиждень, при цьому на семи виробничих комплексах зайнято 5 робочих на повних ставках і 2 робочих працюють тимчасово (по 15 годин на тиждень). Відповідно до трудового законодавства на подібному виробництві може бути відпрацьовано 230 годин на тиждень.

Після виробництва продукція надходить на ділянку очищення, де на семи комплексах зайнято 6 робочих на повній ставці і 1 робочий працює тимчасово (по 10 годин на тиждень). Всього на ділянці очищення може бути відпрацьовано 250 годин на тиждень.

Витрати часу (в годинах) на виробництво і очищення наведені в табл. 7.1.

Таблиця 7.1 – Дані компанії «Промрозчин»




С1

С2

Виробництво, годин

2

1

Очищення, годин

1

2

Витратних матеріалів достатньо для виробництва необмеженої кількості розчинів, попит на розчин С1 практично необмежений, а попит на
С2 – 120 000 л на тиждень. Ціна продажу розчину С1 – 150 грн за 1000 л, а С2 – 250 грн. Оскільки всі робочі отримують фіксовану зарплатню незалежно від кількості відпрацьованих годин, то ці витрати є фіксованими і не включені до доходу компанії.

Необхідно визначити, яким чином компанія може підвищити свій прибуток.


Завдання 4 Невелика фірма „Паті-гласс” виробляє скляний посуд на замовлення партіями – набори фужерів для соку і коктейлів. Для виробництва такого посуду фірма закупила спеціальне устаткування, виробнича лінія якого може бути налаштована на виробництво фужерів або для соку, або для коктейлів. Перемикання устаткування з одного на інший тип продукції відбувається достатньо швидко, тому під час планування ним можна знехтувати. За 6 годин виробництва фужерів для соку може бути виготовлено 100 наборів. Що ж стосується виробництва фужерів для коктейлів, то 100 їх наборів буде виготовлено за 5 годин. Протягом тижня устаткування може бути зайняте не більше 60 годин. Виготовлена продукція зберігається на складі фірми місткістю 1 500 м3. Пакунок з набором фужерів для соку займає 1 м3, а пакунок з набором для коктейлів — 2 м3.

Набори для соку продаються за ціною 25 грн, набори для коктейлів – 22 грн. Проте попит на набори для соку не перевищує 800 штук на тиждень, тоді як усі виготовлені набори для коктейлів продаються протягом тижня.

Менеджерові фірми необхідно найкращим чином спланувати тижневий виробничий план.


Завдання 5 Магазин продає два види безалкогольних напоїв: фанту і квас. Дохід від однієї банки фанти складає 50 коп, а від квасу – 70 коп. У середньому магазин продає не більше 500 банок обох видів напоїв щоденно. Не дивлячись на те, що „Фанта” – напій відомої торгової марки, покупці віддають перевагу квасові, оскільки він є значно дешевшим і смачнішим. Відділом продажу визначено, що об’єми продажу фанти і квасу в натуральному численні повинні співвідноситись не менше ніж 2:1. Крім того, відомо, що магазин продає не менше 100 банок фанти щодня.

Як керівництву магазину найкращим чином спланувати запаси напоїв на початку дня?


Завдання 6 Меблева фабрика для збирання столів і стільців запрошує до роботи чотирьох столярів на 10 днів. Кожен столяр витрачає 2 години на збирання столу і 30 хвилин – на збирання стільця. Покупці зазвичай придбають разом зі столом від чотирьох до шести стільців. Дохід від одного столу складає 750 грн, від одного стільця – 250 грн. На фабриці встановлено 8годинний робочий день.

Керівництво фабрики хотіло б оптимізувати своє виробництво.


Завдання 7 Банк протягом декількох місяців планує вкласти до 1 млн грн у кредитування приватних осіб і купівлі автомобілів. Банківські комісійні складають 14% у випадку кредитування приватних осіб і 12% – купівлі автомобілів. Обидва типи кредитів повертаються в кінці річного періоду кредитування. Відомо, що 3% клієнтських і 2% автомобільних кредитів ніколи не повертаються. Об'єми кредитів на покупку автомобілів зазвичай більше ніж у 2 рази перевищують об'єми кредитів для приватних осіб.

Керівництво банку хотіло б знати, як можна оптимізувати розміщення коштів за вказаними типами кредитів.


Завдання 8 Завод виготовляє 2 типи мікросхем, кожен на окремій лінії. Продуктивність цих ліній складає 600 і 750 мікросхем щодня. Для виробництва мікросхем першого типу необхідно 10 одиниць комплектуючого, а другого типу – 8 одиниць такого самого комплектуючого. Постачальник може забезпечити 8 000 одиниць комплектуючого щоденно. Дохід від мікросхем першого типу складає 300 грн, а другого – 200 грн.

Яким чином можна оптимально спланувати виробництво?


Завдання 9 Меблева фабрика збирає з готових комплектуючих 2 види кухонних шаф: звичайні і «Люкс». Звичайна шафа покривається білою фарбою, а «Люкс» – лаком. Фарбування і покриття лаком виконується на одній виробничій фарбувальній ділянці. Збиральна лінія фабрики щодня може зібрати не більше 200 звичайних шаф і 150 шаф типу «Люкс». Лакування шафи «Люкс» вимагає удвічі більше часу, ніж фарбування однієї простої шафи. Якщо фарбувальна ділянка зайнята тільки лакуванням, то за день тут можна підготувати 180 шаф типу «Люкс». Фабрика оцінює дохід від звичайних шаф і шаф «Люкс» в 500 і 700 грн відповідно.

Складіть оптимальний щоденний розклад роботи фарбувальної ділянки.


Завдання 10 Цех головних уборів випускає капелюхи двох типів: А і В. Пошив капелюха першого типу вимагає в 2 рази більше часових ресурсів, ніж пошив капелюха другого типу. Якби цех випускав тільки капелюхи типу В, добовий об'єм виробництва міг би скласти 400 таких капелюхів. Ринок накладає обмеження: добовий об’єм збуту капелюхів типу А складає не більше 150 одиниць, а капелюхів типу В – 200 одиниць. Дохід від виробництва капелюхів типу А складає 40 грн, а капелюхів типу В – 25 грн. Визначити, як найкращим чином спланувати капелюхове виробництво.


Завдання 11 Компанія випускає два види продукції: А і В. Об’єм продажу продукції А складає не менше 80% від загального об’єму продажу продукції А і В. При цьому компанія не може випускати більше 100 одиниць продукції А щоденно. Для виробництва цієї продукції використовується одна і та сама сировина, надходження якої є обмеженим (240 кг на день). На виготовлення одиниці продукції А витрачається 2 кг сировини, а продукції В – 4 кг. Ціна однієї одиниці продукції А і В складає 100 і 250 грн відповідно.

Як керівництву побудувати оптимальну структуру виробництва компанії?


Завдання 12 Компанія має можливість рекламувати свою продукцію на місцевому радіо і по телебаченню. Бюджет на рекламу є обмеженим (50 000 грн на місяць). Одна хвилина рекламного часу на радіо коштує 75 грн, а по телебаченню – 1500 грн. Компанія припускає, що реклама на радіо за часом повинна перевищувати рекламу по телебаченню не менше ніж у 2 рази. Разом з тим відомо, що неефективно використовувати рекламу на радіо в об'ємі, що перевищує 400 хвилин на місяць. Останні дослідження показали, що реклама на телебаченні є в 25 разів ефективнішою за рекламу на радіо.

Як оптимальним чином спланувати рекламу?


Завдання 13 Компанія „Меблідрев” випускає столи і стільці або з масиву дуба, або з масиву сосни. Компанія має в своєму розпорядженні 150 м2 дуба і 210 м2 сосни. Для виробництва одного столу потрібно або 17 м2 дуба, або 30 м2 сосни. Для виробництва одного стільця необхідно або 5 м2 дуба, або 13 м2 сосни. Вартість одного столу складає 200 грн, одного стільця – 70 грн. Потрібно визначити, яким чином компанія „Меблідрев” може максимізувати свій прибуток.


Завдання 14 Концерн „Пивовар” випускає звичайне пиво і пиво „Ель”, і продає за ціною 25 і 10 грн за декалітр відповідно. Для виробництва одного декалітра пива необхідно 5 кг зерна і 2 кг хмелю, а для виробництва пива «Ель» - 2 кг зерна і 1 кг хмелю. Концерн у своєму розпорядженні має 60 кг зерна і 25 кг хмелю. Необхідно визначити, яким чином концерн може збільшити свій прибуток.


Завдання 15 Компанія «Еліта» випускає чоловічі сорочки і жіночі блузи. Торгова мережа приймає всю продукцію, вироблену компанією. Виробництво швейного виробу складається з розкрою, пошиття і упаковки готового виробу. На ділянці розкрою працює 25 осіб, безпосередньо на пошитті виробів – 35 осіб і 5 осіб зайнято на упаковці. Компанія працює в одну зміну (8 годин) п’ять днів на тиждень. Трудовитрати (у хвилинах на виріб) і дохід від них наведені в табл. 7.2.


Таблиця 7.2 – Дані компанії «Еліта»

Виріб

Операція

Дохід

(грн. на виріб)

Розкрій

Пошив

Упаковка

Сорочка

20

70

12

12,50

Блуза

60

60

4

16


Компанії необхідно найкращим чином спланувати своє виробництво.


Завдання 16 Завод побутової хімії виробляє 2 види миючих засобів: А і В, використовуючи при цьому сировину 1 і 2. Обробка однієї одиниці сировини 1 коштує 40 грн, у результаті виробляється 0,5 одиниці засобу А і стільки ж засобу В. Обробка однієї одиниці сировини 2 коштує 25 грн, в результаті виходить 0,6 одиниць засобу А і 0,4 одиниці засобу В. Щоденне виробництво засобу А повинне складати не менше 10 і не більше 15 одиниць. Аналогічні обмеження для засобу В складають 12 і 20 одиниць.

Як найкращим чином спланувати випуск миючих засобів?


Завдання 17 Меблева фірма «Диво-майстер» випускає і продає столи і шафи з деревини хвойних і листяних порід. Витрата кожного виду деревини в кубометрах на кожен виріб наведена в табл. 7.3.


Таблиця 7.3 – Дані фірми «Диво-майстер»




Хвойні, м3

Листяні, м3

Ціна виробу,

тис. грн.

Стіл

0,15

0,2

1,6

Шафа

0,3

0,1

3,0

Запас деревини

80

40





Менеджеру фірми необхідно визначити оптимальний виробничий план для отримання максимального доходу.


Завдання 18 Підприємство електронної промисловості випускає дві моделі приймачів, причому кожна модель виробляється на окремій технологічній лінії. Добовий об’єм виробництва на першій лінії – 60 виробів, на другій – 75 виробів. На радіоприймач першої моделі витрачається 10 однотипних елементів електронних схем, другої – 8 таких самих елементів. Максимальний добовий запас використовуваних елементів дорівнює 800-ам одиницям. Прибуток від реалізації одного радіоприймача першої і другої моделей складає відповідно 150 і 100 грн. Необхідно визначити оптимальний добовий виробничий план.


Завдання 19 Вироби чотирьох типів проходять послідовну обробку на двох верстатах. Час обробки одного виробу кожного типу на кожному з верстатів наведений в табл. 7.4.

Таблиця 7.4 – Час обробки виробів

Верстат

Час обробки одного виробу, год.

Тип 1

Тип 2

Тип 3

Тип 4

1

2

3

4

2

2

3

2

1

2


Витрати на виробництво одного виробу кожного типу є прямопропорційними до часу завантаження верстатів (у машиногодинах). Вартість машиногодини складає 50 і 75 грн відповідно для 1-го і 2-го верстатів. Допустимий час використання верстатів для обробки виробів усіх типів обмежений наступними значеннями: 500 машиногодин для верстата 1 і 380 машиногодин для верстата 2. Ціни виробів типів 1, 2, 3 і 4 відповідно 325, 350, 275 і 225 грн. Складіть оптимальний план виробництва, який би максимізував чистий прибуток.


Завдання 20 Промислова компанія випускає два види виробів. Виробництво кожного виробу складається з послідовного виконання трьох операцій. Час використання цих операцій для виробництва даних виробів обмежений 10-ма годинами на добу. Час обробки і прибуток від продажу одного виробу кожного виду наведені в табл. 7.5. Знайти оптимальний об’єм виробництва виробів кожного виду.


Таблиця 7.5. – Час обробки і прибуток від продажу одного виробу

Виріб

Час обробки одного виробу, хвилин

Питомий прибуток, грн.

Операція 1

Операція 2

Операція 3

1

10

6

8

10

2

5

20

15

15



Лабораторна робота №8

^ РОЗВ’ЯЗАННЯ ЛІНІЙНИХ ЗАДАЧ ТРАНСПОРТНОГО ТИПУ


Мета роботи – навчитися розв’язувати транспортні задачі з використанням методу потенціалів.

У результаті виконання роботи студент повинен:

ЗНАТИ алгоритм методу потенціалів;

УМІТИ здійснювати побудову початкового плану методом північно-західного кута або мінімального елемента;

МАТИ УЯВЛЕННЯ про виконання критерію оптимальності.


У загальному вигляді задача транспортного типу може бути сформульована таким чином: є пунктів виробництва (іноді їх називають пунктами відправлення) з обсягами виробництва, що дорівнюють відповідно. Розглядається також пунктів споживання (пунктів призначення) з обсягами споживання (попитом) відповідно. Відомі транспортні витрати щодо перевезення одиниці продукції з кожного пункту виробництва в кожний з пунктів споживання: вартість перевезення одиниці продукції з пункту виробництва в пункт споживання  ( ). Задача полягає у визначенні плану перевезення продукції з пунктів виробництва в пункти споживання, що мінімізує сумарні транспортні витрати й задовольняє обмеженням на обсяги пропозиції та попиту.

Матриця транспортних витрат (тарифів) позначається через . Необхідно визначити матрицю перевезень (змінних) , де кількість одиниць продукції, які необхідно доставити з і-го пункту виробництва в -й пункт споживання. Передбачається, що всі .

З урахуванням уведених позначень математична модель транспортної задачі (ТЗ) набуває вигляду:



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


Пункт виробництва

Обсяг виробництва

Пункт споживання





……



Обсяг споживання





……















……

















……





……

……

……

……




……













……





Транспортну таблицю називають іноді табличною або матричною моделлю транспортної задачі.

Необхідно відзначити цілочисловий характер транспортної задачі (в першу чергу її розв’язку), тому транспортні задачі відносяться також до цілочислового програмування, для якого теж існують спеціальні алгоритми розв'язання.

Для того щоб транспортна задача мала припустимі плани необхідним і достатнім є виконання рівності

.

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

Якщо виконується одна з умов:

а) надвиробництво ;

б) дефіцит,

то модель транспортної задачі називають відкритою (незбалансованою). Для можливості розв'язання транспортної задачі з відкритою моделлю необхідно перетворити її на закриту:

    1. За виконання умови a) необхідно ввести -й фіктивний пункт споживання, обсяг попиту якого дорівнює величині дисбалансу . Відповідні вартості перевезень покладаються рівними нулю або, за наявності додаткової інформації, відповідним до значень штрафів за зберігання продукції на складі виробника тощо.

    2. За виконання умови б) уводиться фіктивний пункт виробництва, обсяг виробництва якого дорівнює величині дисбалансу . Вартості перевезень від цього фіктивного постачальника покладаються рівними нулю або, за наявності додаткової інформації, відповідними до значень штрафів за недопоставку продукції тощо. Наприклад, щоб гарантувати задоволення попиту певного пункту споживання, в задачі з умовою дефіциту можна призначити дуже високу вартість перевезень (штраф) від фіктивного пункту виробництва до цього пункту споживання.

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

Загальна транспортна модель із пунктами відправлення й пунктами призначення має обмежень у вигляді рівностей. Оскільки транспортна модель завжди може бути збалансованою, то одна з цих рівностей є надлишковою. Таким чином, транспортна модель має незалежних обмежень і, отже, початковий базисний розв’язок складається з базисних змінних.

Спеціальна структура транспортної моделі дозволяє використовувати спеціальні методи побудови початкового розв’язку.

^ 1 Метод північно-західного кута

Відповідно до даного методу запаси першого постачальника використовуються для задоволення потреб споживачів доки не будуть вичерпані, після чого переходять до запасів наступного постачальника. Якщо в чергову комірку (ij) треба поставити перевезення, а ітий постачальник або jтий споживач має нульовий запас або попит, то в комірку ставиться нуль (базисний нуль).

Виконання побудови початкового опорного плану методом північно-західного кута починається з верхньої лівої комірки транспортної таблиці, тобто зі змінної х11.

Змінній х11 присвоюється максимальне значення, яке допускається обмеженнями на попит і пропозицію.

Далі викреслюється рядок (або стовпчик з повністю реалізованою пропозицією (с задоволеним попитом). Це означає, що в викресленому рядку (стовпчику) значення іншим змінним не присвоюються. Якщо одночасно задовольняється попит і пропозиція, викреслюється тільки рядок або тільки стовпчик.

Якщо не викреслено тільки один рядок або тільки один стовпчик, процес припиняється. У протилежному випадку необхідно перейти до комірки праворуч, якщо викреслений стовпчик, або до комірки, що знаходиться нижче, якщо викреслений рядок. Потім повертаються до попереднього кроку.

Таблиця 8.1 – Приклад побудови опорного плану з використанням методу північно-західного кута

bj (попит)


ai (пропозиції)

30

100

40

110

60

4

30

5

30

2


3


100

1


3

70

6

30

2


120

6


2


7

10

4

110

Заповнено 6 клітинок (=3+4-1), тобто план є базисним.

Відповідно сумарна вартість перевезень складає 4*30+5*30+3*70+
+6*30+7*10+4*110=1170 грошових одиниць.

Недоліком цього методу є те, що він не враховує значення матриці транспортних витрат, в результаті чого отриманий цим методом початковий розподіл може бути дуже далеким від оптимального.


^ 2 Метод мінімального елемента (метод мінімальної вартості)

1 У транспортній матриці визначається комірка з найменшою вартістю перевезення (якщо таких комірок декілька, вибір серед них є довільним).

2 Даній комірці присвоюється максимально можливе значення перевезення, що допускається обмеженнями на попит та пропозицію.

3 Далі виключається з розгляду (викреслюється) рядок (стовпчик), відповідний до пункту виробництва (споживання), обмеження для якого виконано повністю (вичерпаний запас продукції або задоволений попит). Відповідно до привласненого значення змінної корегуються величини пропозиції (попиту), що залишилися незадоволеними.

4 Якщо одночасно задовольняються обмеження щодо пропозиції та попиту, тобто можуть бути одночасно виключені рядок і стовпчик, то викреслюється тільки рядок або тільки стовпчик. При цьому обсяг попиту (пропозиції), відповідний до невикресленого стовпчика (рядка), покладається рівним нулю.

5 Переглядаються невикреслені комірки і обирається серед них нова комірка з мінімальною вартістю. Далі відбувається повернення до пункту 2. Процес триває доти, доки не залишиться лише один невикреслений рядок або стовпчик і не будуть виконані всі обмеження щодо попиту та пропозиції. У результаті утворюється припустимий план, який містить заповнених комірок.


Таблиця 8.2 – Приклад побудови опорного плану з використанням методу мінімального елемента

bj(попит)


ai (пропозиції)

30

100

40

110

60

4


5



2

40

3

20

100

1

30

3


6


2

70

120

6


2

100

7


4

20

Порядок заповнення комірок (2;1), (3;2).(1;3),(2;4),(1;4),(3;4).

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

Найчастіше для розв’язання ТЗ застосовується метод потенціалів, за яким відповідно до кожного і-того рядка (і-го постачальника) встановлюється потенціал ui, а кожного стовпчика j (j-го споживача) встановлюється потенціал vj.
1   2   3   4   5   6   7   8



Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації