Екстремальні завдання
Нагадаємо, що латинське слово extremumозначає "крайнє". Воно в математиці має два конкретні значення: maximum(скорочено max) - найбільше та minimum(скорочено min) - Найменше. У такому розумінні extremumмає більше вузький змістчим optimum, що перекладається від латинського як "найкраще".Завдання знаходження максимального чи мінімального значення заданої функціїна заданій множині називається екстремальним завданням.
Є два види екстремальних завдань – завдання на максимум та завдання на мінімум. Символічно вони записуються так:
Функція f(x) називається цільовою функцією, а Х - безліччю допустимих рішень. Оптимальним рішеннямзадач називається пара (x*,f(x*)) , де x* - точка максимуму (мінімуму), а f(x*) , - значення функції f у цій точці, тобто її максимальне (мінімальне) значення на множині Х.
Вирішити завдання це означає: або знайти оптимальне вирішення; або переконатися, що оптимального рішення немає.
Вирішення завдання потребує вирішення трьох проблем: 1) проблему існування оптимального рішення; 2) проблему встановлення необхідних та достатніх ознак оптимальності (тобто характерних властивостей, властивих точкам максимуму та мінімуму); 3) проблему чисельного обчислення оптимальних рішень.
Приклад №1. Побудувати математичну модельнаступного завдання економічної діяльності. Для цього:
- Виявити проблему та сформулювати мету дослідження.
- Провести опис змінних економічного процесу чи об'єкта.
- Записати математичне формулювання функції мети.
- Сформулювати обмеження завдання, що накладаються умовами, і записати систему обмежень.
- Запропонувати метод розв'язання.
Перед проектувальниками автомобіля поставлено завдання сконструювати найдешевший кузов, використовуючи листовий матеріал, скло та пластмасу. Основні характеристики матеріалів представлені у таблиці.
| Характеристики | Матеріали | ||
| Метал | Скло | Пластмаса | |
| Вартість (тис. руб./м2) | 25 | 20 | 40 |
| Маса (кг/м2) | 10 | 15 | 3 |
Загальна поверхня кузова (разом з дверима та вікнами) повинна становити 14 м2: з них не менше 3,5 м2 і не більше 5 м2 слід відвести під скло. Маса кузова має перевищувати 150 кг, а маса пластмаси має перевищувати 20% від маси кузова. Металева складова поверхні кузова має перевищувати скляну поверхнюне менше, ніж удвічі. Скільки металу, скла та пластмаси має використати найкращий проект.
Проблема полягає в обмежених ресурсахдля отримання оптимального результату.
Опис змінних.
x 1 - кількість металу, м 2
x 2 - кількість скла, м 2
x 3 - кількість пластмаси, м 2
Функція цілі.
Обмеження:
- Загальна поверхня кузова
x 1 + x 2 + x 3 ≥ 14 - Вимоги до скла
x 2 ≥ 3,5
x 2 ≤ 5 - Обмеження по масі
10x 1 + 15x 2 + 3x 3 ≤ 150 - Вимоги щодо маси пластмаси
3x 3 ≤ (10x 1 + 15x 2 + 3x 3)*20% - Обмеження на поверхні
x 1 ≥ 2x 2
Система обмежень.
x 1 + x 2 + x 3 ≥ 14
10x 1 + 15x 2 + 3x 3 ≤ 150
2x 1 + 3x 2 - 2,4x 3 ≥ 0
x 1 - 2x 2 ≥ 0
x 2 ≥ 3,5
x 2 ≤ 5
x 1 , x 2 , x 2 ≥ 0
F(x) = 25x 1 + 20x 2 + 40x 3 → min
Приклад №2. На фабриці виготовляється тканина двох артикулів. Кожна з цих тканин проходить послідовну обробкуна верстатах їх трьох типів. Нижче наведено: продуктивність верстата кожного типу при виготовленні тканин артикулів 1 і 2; сумарні потужності верстатного парку фабрики для одного робочого тижня; трудові витрати на обслуговування верстатів у хвилинах робочого дня на 1 годину роботи верстата; ціна метра тканини кожного артикулу. Відомо також, що тижневий ресурс трудовитрат обслуговування станків дорівнює 14800 год.
| Тип верстатів | Потужність (тис. год) | Трудовитрати (хв/год) | Продуктивність, м/год | |
| Артикул 1 | Артикул 2 | |||
| 1 | 22 | 10 | 20 | 15 |
| 2 | 40 | 6 | 12 | 6 |
| 3 | 75 | 6 | 6 | 4 |
| Ціна 1 м тканини (тис.руб.) | 18 | 25 | ||
Потрібно скласти тижневий план випуску тканин з метою максимізації прибутку виготовленої продукції, якщо 1 година оплачується в розмірі 5400 рублів, а 1 година простою верстата 1-го типу складає 1800 рублів, 2-го типу складає 2000 рублів, 3-го типу складає 1400 рублів . Вартість сировини до уваги не брати. При розв'язанні задачі слід врахувати, що випуск тканини артикула 1 повинен не менше ніж у 2 рази перевищувати випуск тканини артикула 2.
Опис змінних.
x 1 – випуск тканин артикула 1, м
x 2 - випуск тканин артикула 2, м
y 1 - час роботи 1-го верстата, год.
y 2 - час роботи 2-го верстата, год.
y 3 – час роботи 3-го верстата, год.
y 1 = x 1/20 + x 2/15
y 2 = x 1/12 + x 2/6
y 3 = x 1/6 + x 2/4
x 1, x 2 , y 1 , y 2 , y 3 ≥ 0
Обмеження:
- за структурою випуску
x 1 ≥ 2x 2 - з трудовитрат
10/60y 1 + 6/60y 2 +6/60y 3 ≤ 14800
або
1/6y 1 + 1/10y 2 +1/10y 3 ≤ 14800 - за наявними потужностями:
y 1 ≤ 22000
y 2 ≤ 40000
y 3 ≤ 75000
Функція цілі.
Прибуток = Виручка - Витрати = Ціна*Кількість - Витрати на простий верстат - Трудовитрати
Виторг = 18x1 + 25x2
Витрати на простий верстатів = 1,8y 1 + 2y 1 + 1,4y 3
Трудовитрати = 5,4 (1/6y 1 + 1/10y 2 +1/10y 3)
F(x) = 18x 1 + 25x 2 - 1,8y 1 - 2y 2 - 1,4y 3 - 5,4(1/6y 1 + 1/10y 2 +1/10y 3)→ max
або
F(x) = 1/50 (900x 1 +1250x 2 -135y 1 -127y 2 -97y 3) → max
З урахуванням
y 1 = x 1/20 + x 2/15
y 2 = x 1/12 + x 2/6
y 3 = x 1/6 + x 2/4
маємо:
Система обмежень.
x 1 ≥ 2x 2
1/6(x 1 /20 + x 2 /15) + 1/10(x 1 /12 + x 2 /6) +1/10(x 1 /6 + x 2 /4) ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000
x 1 ≥ 2x 2
x 1 /30+19x 2 /360 ≤ 14800
x 1 /20 + x 2 /15≤ 22000
x 1 /12 + x 2 /6 ≤ 40000
x 1 /6 + x 2 /4 ≤ 75000
F(x) = 17.33x 1 +23.91x 2 → max
Приклад №3. На підприємстві є два цехи. У першому цеху працюють 50 робочих, їх 20 мають 6 розряд і 30 - третій розряд. У другому цеху, зі 100 робочих 50 мають 6 розряд та інші - третій. Потрібно виконати замовлення виготовлення 2 типів деталей. На виготовлення однієї деталі першого типу робітник 6 розряду витрачає 10 хв., а робітник 3 розряду - 15 хв. На виготовлення однієї деталі другого типу робітник 6 розряду витрачає 25 хв, а робітник третього - 30 хв.
13) скласти план випуску продукції для кожного з цехів на тиждень, виходячи зі стандартної тривалості робочого тижня, що максимізує загальний обсяг випуску продукції з урахуванням того, що потреба в деталях другого типу вдвічі менша від потреби в деталях першого типу.
14) Визначити план випуску продукції для кожного з цехів на тиждень, виходячи зі стандартної тривалості робочого тижня, максимізуючи прибуток, з урахуванням того, що робітник 6 розряду отримує 300 руб./міс., а робітник 3 розряду - 200 руб./міс. , при тому, що ціна реалізації деталі 1 типу дорівнює 20 руб. / Шт, а другого типу - 34 руб. / Шт.
Рішення.
x 11 - кількість деталей 1 типу, виготовлені робітниками 6 розряду за тиждень,
x 12 - кількість деталей 2 типу, виготовлені робітниками 6 розряду за тиждень,
x 21 - кількість деталей 1 типу, виготовлені робітниками 3 розряди за тиждень,
x 22 - кількість деталей 2 типу, виготовлені робітниками 3 розряди за тиждень,
13) Цільова функція
20x 11 + 50x 21 + 30x 12 + 50x 22 = max
Обмеження:
2(x 12 +x 22) ≤ x 11 +x 21
14) Цільова функція: Прибуток = Дохід - Витрати = Кількість деталей * Ціна реалізації - ЗП працівників
Витрати заробітну плату робочим приведемо до тижневим, тобто розділимо місячний заробіток на 4.
F(x) = 20(20x 11 + 50x 21) + 23(30x 12 + 50x 22) - [(20+50)*300 + (30+50)*200]/4 = max
Обмеження:
2(x 12 +x 22) ≤ x 11 +x 21
10/60x 11 + 15/60x 21 + 25/60x 11 + 30/60x 21 ≤ N
N - тижневий фонд часу в годиннику.
МАТЕМАТИЧНИЙ ОПИС МОДЕЛІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
МОДЕЛЬ ЛІНІЙНОГО ПРОГРАМУВАННЯ
1 Математичний опис моделі лінійного програмування
2 Методи реалізації моделей лінійного програмування
3 Подвійне завдання лінійного програмування
Модель лінійного програмування(ЛП) має місце, якщо в досліджуваній системі (об'єкті) обмеження на змінні та цільова функція лінійні.
Моделі ЛП використовуються для вирішення двох основних типів прикладних завдань:
1) оптимального планування у будь-яких сферах людської діяльності – соціальної, економічної, науково-технічної та військової. Наприклад, при оптимальному плануванні виробництва: розподіл фінансових, трудових та інших ресурсів, постачання сировини, управління запасами і т.д.
2) транспортного завдання (знаходження оптимального плану різного роду перевезень, оптимального плану розподілу різних засобівпо об'єктах різного призначенняі т.п.)
МАТЕМАТИЧНИЙ ОПИС МОДЕЛІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Потрібно знайти невід'ємні значення змінних
задовольняють лінійним обмеженняму вигляді рівностей та нерівностей
,
де 
– задані числа,
та забезпечують екстремум лінійної цільової функції
,
де – задані числа, що записується у вигляді
Допустимим рішеннямназивається будь-яка сукупність 
, що задовольняють умовам.
Область допустимих рішень- Безліч всіх допустимих рішень.
Оптимальне вирішення 
, для котрого 
.
Зауваження
1. Наведена модель ЛП є загальної. Розрізняють також стандартніі канонічніформи моделей ЛП.
2. Умови існуванняреалізації моделі ЛП:
- Безліч допустимих рішень - не порожнє;
- цільова функція 
обмежена на (хоча зверху при пошуку максимуму і знизу при пошуку мінімуму).
3.ЛП ґрунтується на двох теоремах
Теорема 1. Безліч G, що визначається системою обмежень виду, є опукле замкнуте безліч ( опуклий багатогранникз кутовими точками - вершинами.)
Теорема 2.
Лінійна форма 
, визначена на опуклому багатограннику
j=1,2,…,s
i=s+1,s+2,…, m,
досягає екстремуму в одній із вершин цього багатогранника.
Ця теорема отримала назву теореми про екстремум лінійної форми.
Відповідно до теореми Вейєрштраса оптимальне рішення єдине і є глобальним екстремумом.
Існує загальний аналітичний підхіддля реалізації моделі ЛП – симплекс-метод. При вирішенні завдань лінійного програмування досить часто рішення немає. Це відбувається з таких причин.
Першу причину проілюструємо прикладом
Про таку причину кажуть, що обмеження є несумісними. Область допустимих рішень – безліч.
Друга причина коментується наступним прикладом:
У даному випадкуобласть допустимих рішень не обмежена зверху. Область допустимих рішень не обмежена.
Наслідуючи традиції лінійного програмування, дамо задачі ЛП економічну інтерпретацію. Нехай у нашому розпорядженні є mтипів ресурсів Кількість ресурсу типу jодно. Ці ресурси необхідні виробництва nтипів товарів. Позначимо кількість цих товарів символами 
відповідно. Одиниця товару типу iстоїть. Виробництво товарів типу iмає бути обмежено величинами 
відповідно. Виробництво одиниці товару типу iвитрачається ресурсу типу j. Необхідно визначити такий план виробництва товарів ( 
), щоб їхня сумарна вартість була мінімальною.
Завдання лінійного програмування, що використовуються для оптимізації функціонування реальних об'єктів, містять значну кількість змінних та обмежень. Це зумовлює неможливість вирішення їх графічними методами. При великому числі змінних та обмежень застосовуються методи алгебри, в основі яких лежать ітераційні обчислювальні процедури. У лінійному програмуванні розроблено безліч методів алгебри, що різняться між собою способами побудови початкового допустимого рішення і умовами переходу від однієї ітерації до іншої. Однак ці методи базуються на загальних теоретичних положеннях.
Спільність основних теоретичних положень призводить до того, що методи алгебри вирішення завдань лінійного програмування багато в чому подібні між собою. Зокрема, практично будь-який вимагає попереднього приведення завдання лінійного програмування до стандартної (канонічної) формі.
Алгебраїчні методи розв'язання задачі ЛП починаються з приведення її до стандартній (канонічній) формі:
,
,
i=1,..,n;j=1,..,m.
Будь-яка задача лінійного програмування може бути приведена до стандартної форми. Порівняння загальної моделіз канонічною моделлю дозволяє зробити висновок про те, що для приведення завдання ЛП до стандартної форми необхідно, по-перше, від системи нерівностей перейти до рівностей, а по-друге, перетворити всі змінні так, щоб вони були негативними.
Перехід до рівностей здійснюється додаванням до лівої частини обмежень невід'ємної залишкової змінної для нерівностей типу, і відніманням з лівої частини невід'ємної надлишкової змінної для нерівностей типу. Наприклад, нерівність 
при переході до стандартної форми перетворюється на рівність 
, a нерівність 
- у рівність 
. У цьому, як залишкова змінна , і надлишкова змінна є неотрицательными.
Передбачається, що права частинанерівностей невід'ємна. Інакше цього можна домогтися множенням обох частин нерівності на «-1» і зміною його знака на протилежний.
Якщо у вихідному завданні лінійного програмування змінна не обмежена у знаку, її можна подати у вигляді різниці двох невід'ємних змінних 
, де 
.
Важливою особливістюзмінних 
є те, що при будь-якому допустимому рішенні тільки одна з них може набувати позитивного значення. Це означає, що якщо 
, то 
і навпаки. Отже, може розглядатися як залишкова, а як надмірна змінні.
прикладНехай дане завдання лінійного програмування:
,
.
Потрібно привести її до стандартної форми. Зауважимо, що перша нерівність вихідного завдання має знак , отже, в нього необхідно ввести залишкову змінну . В результаті отримаємо.
Друга нерівність має знак і для перетворення до стандартної форми вимагає введення надмірної змінної, виконавши цю операцію, отримаємо.
Крім того, змінна не обмежена у знаку. Отже, як у цільовій функції, так і в обох обмеженнях вона повинна бути замінена на різницю 
. Виконавши підстановку, отримаємо завдання лінійного програмування у стандартній формі, еквівалентну вихідному завданню:
.
Завдання лінійного програмування, записане в стандартній формі, є завданням пошуку екстремуму цільової функції на безлічі векторів, які є рішеннями системи. лінійних рівняньз урахуванням умов невід'ємності. Як відомо, система лінійних рівнянь може мати рішень, мати єдине рішення чи мати безліч рішень. Оптимізація цільової функції можлива лише у тому випадку, якщо система має нескінченнебезліч рішень. Система лінійних рівнянь має безліч рішень, якщо вона спільна (ранг основної матриці дорівнює рангурозширеною) і, якщо ранг основної матриці менший від числа невідомих.
Нехай ранг матриці системи обмежень дорівнює m. Це означає, що матриця має хоч один мінор m-го порядку не дорівнює нулю. Не порушуючи спільності, можна припустити, що мінор розташований у лівому верхньому куткуматриці. Цього завжди можна досягти, змінивши нумерацію змінних. Цей не рівний нулю мінор рангу mприйнято називати базисним. Складемо систему з перших mрівнянь системи, записавши її так:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Розглянуті вище моделі можна віднести до розряду статичних моделей лінійного програмування, оскільки в них часовий інтервал фіксувався. Якщо виникає необхідність знайти рішення для іншого тимчасового інтервалу, то потрібно заново вводити дані в модель та виробляти нову оптимізацію. Інакше висловлюючись, у підході, розглянутому вище, передбачалося, що це тимчасові інтервали є незалежними й у кожного тимчасового інтервалу має вирішуватися своє завдання оптимізації.
У динамічних моделяхрозглядається поведінка системи на декількох часових інтервалах, а пошук рішення проводиться один раз, оптимізуючи поведінку моделі на всіх часових інтервалах одночасно.
Динамічні моделі є більш реалістичними і адекватніше описують багато виробничі ситуації. Залежність прийняття рішення від поведінки системи в часі робить динамічні моделі виключно корисним методом економічного аналізу, але вони виявляються значно складнішими за статичні за своєю постановкою, містять, як правило, велике числозмінних, вимагають певного навички при складанні табличної моделі.
Як приклад розглянемо практично значущу модель управління виробничими запасами (інша назва цієї моделі – багатофазові моделі управління запасами). Для спільності результатів ми не присвоюватимемо параметрам числові значення. Після побудови моделі можна буде задати явні значення параметрів та отримати чисельне рішення.
Приклад 3.10
Розглянемо хімічну фірму, яка виробляє поліуретан. Виробник має замовлення на постачання поліуретану у кількості d i тонн на місяць на найближчі чотири місяці (i=1,2,…,4). Нехай витрати на виробництво однієї тонни поліуретану становлять C i тис. рублів, а максимальний обсяг виробництва поліуретану по місяцях обмежений і дорівнює K i тонн на місяць. Виробнича фірма має можливість зберігати продукцію складі, причому вартість зберігання однієї тонни продукції протягом місяця становить n і тис. рублів. На початковий період запас поліуретану на складі становив L 0 тонн. Менеджеру компанії потрібно скласти план виробництва поліуретану по місяцях, який би забезпечив виконання замовлень за мінімальної вартості виробництва та зберігання продукту.
Рішення
Зауважимо, що якби не було можливості зберігати продукцію на складі, то завдання розбилося б на чотири незалежні статичні завдання і втратило б для нас будь-який сенс.
Складемо рівняння матеріального балансу, що дозволяє обчислити кількість продукції, що зберігається складі протягом i-го місяці. Нехай x i – кількість поліуретану, виробленого в i-й тимчасовоїперіод. Тоді протягом першого місяця товарний запас на складі дорівнюватиме L 1 =L 0 +x 1 -d 1 . Товарний запас другого місяця
Продовжуючи цей процес, легко отримати загальну формулутоварних запасів для будь-якого часового інтервалу:
. (3.24)
Після того як ми вивели рівняння (3.24), що описує поведінку товарних запасів, легко записати математичну модель завдання:
(3.25)
Поставлене завдання (3.25) є типовим завданням лінійного програмування і може бути досить легко вирішено за допомогою програми Пошук рішення.Використовуючи чисельні значення питомих витрат виробництва
та необхідного обсягу поставок та виробничих потужностей по місяцях
потрібно скласти оптимальний план виробництва поліуретану, якщо першого січня запас поліуретану складі становив 15 тонн.
Таблична модельзавдання управління запасами
Таблична модель завдання після знаходження оптимального рішення наведено на рис. 21.
Мал. 21. Таблична модель завдання динамічного програмування
Слід сказати кілька слів і про звіт стійкості для цієї моделі, наведений на рис. 22.
Мал. 22. Звіт зі стійкості для динамічної моделі
Якщо використовується просте обмеження на значення змінних, що оптимізуються (x i ≤K i в нашому випадку), то у звіті за стійкістю тіньові ціни для цих обмежень містяться в стовпці нормована вартість, а інформація про допустимий діапазон тіньових цін для цих обмежень не виводиться. Таким чином, якщо збільшити на одну тонну виробничі потужності у січні, то загальні витрати зменшаться на 1,7 тис. рублів.
Вимагає додаткових пояснень та стовпець Цільовий коефіцієнтзвіту щодо стійкості. Наведені тут значення Excelобчислює самостійно. Сенс цільового коефіцієнта при змінній у тому, що він показує, наскільки збільшиться значення цільової функції зі збільшенням оптимального значеннязмінної на одиницю.
У цьому легко переконатись на практиці. Оптимальне значення виробництва поліуретану у січні – 60 тонн, а сумарні витрати дорівнюють 4 776,45 тис. рублів. Якщо оптимального значення за січень підставити число 61 і перерахувати сумарні витрати, то отримаємо нове значення – 4 805,50. Різниця цих чисел якраз і дорівнює 29,05 – цільовому коефіцієнту при змінній обсягу виробництва, у січні.
Широко відомі інші постановки завдань динамічного програмування. Деякі з них (модель заміни обладнання та модель інвестицій) будуть розглянуті на практичних заняттях.
Математичне програмування( " планування " ) – це розділ математики, що займається розробкою методів відшукання екстремальних значень функції, аргументи якої накладені обмеження. Ідея лінійного програмування виникла 1939 р., коли було надруковано брошуру Леоніда Віталійовича Канторовича " Математичні методиорганізації та планування виробництва". Американський математик А. Данциг у 1947 році розробив дуже ефективний конкретний методчисельного розв'язання задач лінійного програмування (він отримав назву симплекс методу ).
Подальше викладення матеріалу передбачає, що студенти вивчали теорію лінійного програмування в курсі математики. У зв'язку з цим рекомендується поєднувати читання цього розділу із переглядом презентацій. Електронні версії презентацій розміщені у папці «Лінійне програмування». При цьому частина матеріалу призначена для відновлення знань, отриманих у курсі математики, а частина для їхнього розширення та поглиблення з акцентом на прикладні можливості теоретичних моделей.
Теорія лінійного програмування
Загальна постановка задачі
Ідея лінійного програмування представлена у форматі презентацій, електронна версіяяких розміщено у файлі «Ідея – лінійне програмування».
Геометрична інтерпретація та графічний методрішення
Графічно спосіб розв'язання задач лінійного програмування доцільно використовувати:
1. Для вирішення завдань із двома змінними, коли обмеження виражені нерівностями.
2. Вирішення завдань з багатьма змінними за умови, що в них канонічного записуміститься трохи більше двох вільних змінних.
Геометричний методвирішення завдань лінійного програмування представлений у форматі презентації – файл «Геометричний метод ЛП»
2.2. Симплекс-метод, Загальна характеристика, критерій оптимальності допустимого базисного плану
Графічний спосібРозв'язання задачі лінійного програмування показує, що оптимальне вирішення цього завдання завжди асоціюється з кутовою точкою простору рішень (у математиці вона також називається крайньою точкою множини ). Це є ключовою ідеєю розробки загального алгебраїчного симплекс-метода на вирішення будь-якої завдання лінійного програмування.
Перехід від геометричного способу вирішення задачі лінійного програмування до симплекс-методу лежить через опис алгебри крайніх точок простору рішень. Для реалізації цього переходу спочатку треба навести завдання лінійного програмування до стандартної (канонічної) форми:
· Перетворити нерівності обмежень у рівності шляхом введення додаткових змінних;
· Перетворити вільні змінні на невід'ємні;
· Перетворити завдання максимізації в задачу мінімізації.
Стандартна формаЗавдання лінійного програмування необхідне, тому що вона дозволяє отримати базисне рішення (використовуючи систему рівнянь, породжену обмеженнями). Це (алгебраїчне) базисне рішення повністю визначає всі (геометричні) крайні точки простору рішень. Симплекс-метод дає змогу ефективно знайти оптимальне рішення серед усіх базисних.
Відновити знання щодо вирішення завдань симплекс-методом можна за допомогою презентації «Симплекс метод».
Подвійні завдання
Будь-яке завдання лінійного програмування має подвійну природу. Правило побудови двоїстої задачі:
Якщо вихідне завданняна max, то двоїста на min і навпаки.
У двоїстої задачі стільки змінних, скільки обмежень у вихідній постановці. При цьому змінні відповідають обмеженням та навпаки.
Коефіцієнтами цільової функції двоїстої задачі є праві частини обмежень вихідної задачі.
Матриця коефіцієнтів обмежень двоїстої задачі виходить транспонуванням матриці коефіцієнтів обмежень вихідної задачі.
Правими частинами обмежень двоїстої завдання є коефіцієнти цільової функції вихідної.
Обмеженням нерівностей вихідного завдання відповідають невід'ємні змінні двоїстої задачі, а обмеженням рівності – змінні будь-якого знака і навпаки.
Теорема 1: Якщо вихідна задача має оптимальний план x*, то подвійна задача також має оптимальний план y*, причому значення функцій цих планах рівні: f(x*)=g(y*).
Теорема 2: Якщо вихідна та двоїста задачі мають плани, то вони мають і оптимальні плани, причому f(x*)=g(y*).
Ознаки оптимальності для подвійних завдань:
Ознака 1: Якщо вихідна та двоїста задачі мають плани X та Y, причому f(X)=g(Y), то ці плани оптимальні.
Визначення: Обмеження, розташовані на одному рядку у схемі пари двоїстих завдань, називають сполученими.
Ознака 2: Для того, щоб плани X і Y вихідної та двоїстої задач були оптимальні, необхідно і достатньо щоб на цих планах хоча б одне з кожної пари сполучених обмежень було рівністю.
Друга ознака дозволяє, знаючи оптимальний план одного із завдань, знайти оптимальний план іншого завдання.
Основні положення двоїстої задачі викладені у презентаціях «Теорія двоїстості» та «Двійна задача».
Транспортні завдання
Транспортне завдання є одним із найпоширеніших спеціальних завдань лінійного програмування. Перша сувора постановка транспортного завдання належить Ф. Хічкоку, а перший точний метод рішення розроблений Л. В. Канторовичем та М. К. Гавуріним.
Під назвою " транспортне завдання” об'єднується широке коло завдань із єдиною математичною моделлю. Дані завдання відносяться до завдань лінійного програмування та можуть бути вирішені симплексним методом. Проте матриця системи обмежень транспортного завдання настільки своєрідна, що її вирішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім покращуючи його, отримати оптимальне рішення.
Під терміном " транспортні завдання " розуміється широке коло завдань як транспортного характеру. Спільним для них є, як правило, розподіл ресурсів, що знаходяться у mвиробників (постачальників), за nспоживачам цих ресурсів. Розрізняють два типи транспортних завдань: критерієм вартості(план перевезень оптимальний, якщо досягнуто мінімум витрат на його реалізацію) та за критерієм часу(План оптимальний, якщо на його реалізацію витрачається мінімум часу).
Найчастіше зустрічаються такі завдання, які стосуються транспортних:
· Прикріплення споживачів ресурсу до виробників;
· Прив'язка пунктів відправлення до пунктів призначення;
· Взаємна прив'язка вантажопотоків прямого та зворотного напрямів;
· Окремі завдання оптимального завантаження промислового обладнання;
· оптимальний розподілобсягів випуску промислової продукції між заводами-виробниками та ін.
Постановки завдань транспортного типу, алгоритми їх вирішення та приклади практичного використанняпредставлені у трьох презентаціях:
1. «Узагальнене транспортне завдання (λ-завдання)».
2. «Закрите транспортне завдання. Метод потенціалів».
3. «Ускладнені постановки транспортного завдання».
Економічні програми
Різноманітність економічних програм математичного моделюванняметодами лінійного програмування розглянемо з прикладів формулювання конкретних постановок прикладних завдань (запозичено з курсу лекцій Диязитдиновой А.П.).
Завдання 1
Для збереження нормальної життєдіяльності людина повинна за добу споживати білків не менше 120 умовних одиниць (усл. од.), жирів – не менше 70 та вітамінів – не менше 10 ум. од. Зміст їх у кожній одиниці продуктів П 1 і П 2 дорівнює відповідно (0,2; 0,075; 0) та (0,1; 0,1; 0,1) ум. од.
Вартість 1 од. продукту П 1 - 2 руб., П 2 -3 руб.
Побудуйте математичну модель завдання, що дозволяє організувати харчування, щоб його вартість була мінімальною, а організм отримав необхідну кількість поживних речовин.
Завдання 2
З пункту А до пункту В щодня відправляються пасажирські та швидкі поїзди. Дані про організацію перевезень такі:
Скільки має бути сформовано швидких та пасажирських поїздів, щоб перевезти найбільша кількістьпасажирів?
Завдання 3
Чотири овочесховища щодня забезпечують картоплею три магазини. Магазини подали заявки відповідно на 17, 12 та 32 тонни. Овочесховища мають відповідно 20, 20, 15 та 25 тонн. Тарифи (у т. е. за 1 тонну) вказані в наступній таблиці:
Завдання 4
Є два склади готової продукції: А 1 і А 2 із запасами однорідного вантажу 200 та 300 тонн. Цей вантаж необхідно доставити трьом споживачам У 1 , У 2 та У 3 у кількості 100, 150 та 250 тонн відповідно. Вартість перевезення 1 тонни вантажу зі складу А 1 споживачам У 1 , У 2 та У 3 дорівнює 5, 3, 6 д.е., а зі складу А 2 тим самим споживачам – 3, 4, 2 д.е. відповідно.
Складіть план перевезень, що мінімізує сумарні транспортні витрати.
Завдання 5
При відгодівлі кожна тварина має отримати щонайменше 9 од. білків, 8 од. вуглеводів та 11 од. протеїну. Для складання раціону використовують два види корму, поданих у наступній таблиці.
Вартість 1 кг корму першого виду – 4 д.о., другого – 6 д.о.
Складіть денний раціон поживності, що має мінімальну вартість.
Завдання 6
Господарство має такі ресурси: площа – 100 од., праця – 120 од., тяга – 80 од. Господарство виробляє чотири види продукції: П 1 , П 2 , П 3 та П 4 . Організація виробництва характеризується такою таблицею:
Складіть план випуску продукції, який би господарству максимальну прибуток.
Завдання 7.
Цех випускає трансформатори двох видів. Для виготовлення трансформаторів обох видів використовуються залізо та дріт. Загальний запас заліза – 3 тонни, дроту – 18 тонн. На один трансформатор першого виду витрачаються 5 кг заліза та 3 кг дроту, а на один трансформатор другого виду витрачаються 3 кг заліза та 2 кг дроту. За кожен реалізований трансформатор першого виду завод отримує прибуток 3 д.е., другого – 4 д.е.
Складіть план випуску трансформаторів, що забезпечує заводу максимальний прибуток.
Завдання 8
Радгосп відвів три земельні масиви розміром 5000, 8000 та 9000 га на посіви жита, пшениці, кукурудзи. Середня врожайність у центнерах на 1 га за масивами зазначена у таблиці:
| Посіви | Масиви | ||
| I | II | III | |
| жито | |||
| пшениця | |||
| кукурудза |
За 1 центнер жита радгосп отримує 2 д.о., за 1 центнер пшениці – 2,8 д.е., за 1 центнер кукурудзи – 1,4 д.о. Скільки гектарів і на яких масивах радгосп має відвести на кожну культуру, щоб отримати максимальний виторг, якщо за планом він зобов'язаний здати не менше 1900 тонн жита, 158 000 тонн пшениці та 30 000 тонн кукурудзи?
Завдання 9
З трьох продуктів – І, ІІ, ІІІ складається суміш. До складу суміші має входити не менше 6 од. хімічної речовини А, 8 од. - Речовини В і не менше 12 од. речовини С. Структура хімічних речовин наведена у наступній таблиці:
| Продукт | Вміст хімічної речовини в 1 од. продукції | Вартість 1 од. продукції | ||
| А | У | З | ||
| I | ||||
| II | ||||
| III | 1,5 | 2,5 |
Складіть найдешевшу суміш.
Завдання 10
У школі проводиться конкурс на найкращу стінгазету. Одному школяру дано таке доручення:
купити акварельної фарби за ціною 30 д.о. за коробку, кольорові олівці за ціною 20 д.о. за коробку, лінійки за ціною 12 ВО, блокноти за ціною 10 ВО;
фарб потрібно купити не менше трьох коробок, блокнотів – стільки, скільки коробок олівців та фарб разом, лінійок не більше п'яти. На покупки виділяється щонайменше 300 д.е.
У якій кількості школяр має купити зазначені предмети, щоб загальна кількість предметів була найменшою?
Завдання 11
Є три спеціалізовані майстерні з ремонту двигунів. Їхні виробничі потужності рівні відповідно 100, 700, 980 ремонтів на рік. У п'яти районах, обслуговуваних цими майстернями, потреба у ремонті дорівнює відповідно 90, 180, 150, 120, 80 двигунів на рік. Витрати на перевезення одного двигуна з районів до майстерень такі:
| Райони | Майстерні | ||
| 4,5 | 3,7 | 8,3 | |
| 2,1 | 4,3 | 2,4 | |
| 7,5 | 7,1 | 4,2 | |
| 5,3 | 1,2 | 6,2 | |
| 4,1 | 6,7 | 3,1 |
Сплануйте кількість ремонтів кожної майстерні для кожного з районів, що мінімізує сумарні транспортні витрати.
Завдання 12
Нафтопереробний завод отримує чотири напівфабрикати: 400 тис. л алкілату, 250 тис. л крекінг-бензину, 350 тис. л бензину прямої перегонки та 100 тис. л ізопентону. Внаслідок змішування цих чотирьох компонентів у різних пропорціях утворюються три сорти авіаційного бензину: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Вартість 1 тис. л зазначених сортів бензину характеризується числами 120 ВО, 100 ВО, 150 ВО.
Складіть план випуску різних сортів авіаційного бензину за умови отримання максимальної вартості всієї продукції.
Завдання 13
Для участі у змаганнях спортклуб має виставити команду, що складається зі спортсменів І та ІІ розрядів. Змагання проводяться по Бузі, пряжкам у висоту, стрибкам у довжину. У бігу повинні брати участь 5 спортсменів, у стрибках у довжину – 8 спортсменів, а стрибках у висоту – трохи більше 10. кількість очок, гарантованих спортсмену кожного розряду з кожного виду, зазначено у таблице:
Розподіліть спортсменів у команди так, щоб сума очок команди була найбільшою, якщо відомо, що у команді I розряд мають лише 10 спортсменів.
Завдання 14
Звіроферма вирощує чорно-бурих лисиць та песців. На звірофермі є 10000 клітин. В одній клітці можуть бути або дві лисиці, або один песець. За планом на фермі має бути не менше 3000 лисиць та 6000 песців. Однієї доби необхідно видавати кожній лисиці корму – 4 од., а кожному песцю – 5 од. Ферма щодня може мати трохи більше 200 000 одиниць корму. Від реалізації однієї шкірки лисиці ферма отримує прибуток 10 д.е., а від реалізації однієї шкурки песця - 5 д.е.
Яку кількість лисиць і песців потрібно тримати на фермі, щоб отримати найбільший прибуток?
Завдання 15
Є два елеватори, в яких зосереджено відповідно 4200 та 1200 тонн зерна. Зерна необхідно перевезти трьом хлібозаводам у кількості 1000, 2000 та 1600 тонн кожному. Відстань від елеватора до хлібозаводу вказана в таблиці:
Витрати перевезення 1 тонни товару на 1 км становлять 25 д.е. Сплануйте перевезення зерна за умови мінімізації транспортних витрат.
Завдання 16
З двох сортів бензину утворюються дві суміші – А та В. Суміш А містить Бензину 60% 1-го сорту та 40% 2-го сорту; суміш В - 80% 1-го сорту та 20% 2-го сорту. Ціна 1 кг суміші А - 10 д.е., а суміші В - 12 д.е.
Складіть план утворення сумішей, за якого буде отримано максимальний дохід, якщо є бензин 50 т 1-госорта і 30 т другого сорту.
Завдання 17
Є дві ґрунтово-кліматичні зони, площі яких відповідно дорівнюють 0,8 та 0,6 млн. га. Дані про врожайність зернових культур наведено у таблиці:
Визначте розміри посівних площ озимих та ярих культур, необхідні досягнення максимального виходу продукції вартісному вираженні.
Завдання 18
На заводі виготовляють вироби чотирьох типів. Від реалізації 1 од. кожного виробу завод отримує прибуток відповідно 2, 1, 3, 5 тобто. На виготовлення виробів витрачаються ресурси трьох видів: енергія, матеріали, працю.
Дані про технологічному процесінаведено у наступній таблиці:
Сплануйте виробництво так, щоб прибуток від їх реалізації був найбільшим.
