Загальний вигляд задачі лінійного програмування. Різні форми запису задач лінійного програмування

Предмет, особливості та сфери застосування оптимізаційних методів та моделей в економіці

МЕТОДИЧНІ ВКАЗІВКИ ДО КОНТРОЛЬНОЇ РОБОТИ

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

Метою дисципліни «Оптимізаційні методи та моделі» є формування системи знань з методології та інструментарію побудови і використання різних типів оптимізаційних моделей та методів їх дослідження та аналізу.

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

Моделювання – основний специфічний метод науки, що застосовується для аналізу та синтезу систем управління. Для аналізу й синтезу систем управління в економіці використовуються різноманітні економіко-математичні методи та моделі. Моделювання економіки як науковий напрям сформувався у 60-ті роки ХХ століття, хоча має давню й багату передісторію. У його основу, окрім економічних, покладено низку фундаментальних дисциплін (математику, теорію ймовірностей, теорію систем, інформатику, статистику, теорію автоматичного управління).

Окремо серед економіко-математичних моделей варто виділити моделі математичного програмування.

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

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

Функція, мінімум чи максимум якої шукаємо, називається цільовою функцією (критерієм, функціоналом).

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

, (1)

причому вектор повинен задовольняти систему співвідношень (обмежень)

(2)

де – деякі функції, – деякі дійсні числа,

та умову невід’ємності

, . (3)

Вектор , що задовольняє умови (2) і (3), називається допустимим розв’язком або планом задачі.

Числа , що складають план задачі , називаються компонентами плану або параметрами управління.

Множина наборів , , … , що задовольняють умови (2) і (3), називається областю визначення задачі або допустимою областю (допустимим розв’язком задачі).

План задачі , при якому цільова функція набуває мінімуму чи максимуму, називається оптимальним планом або оптимальним розв’язком задачі.

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

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

(4)

за умов

, (5)

(6)

Існує три основні форми запису задачі лінійного програмування загальна, канонічна (основна), стандартна (або симетрична).

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

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

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

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

Задача знаходження найменшого значенння цільової функції еквівалентна до задачі знаходження найбільшого значення функції : .

Приклад 1. Задача про використання та оцінку ресурсів.

Меблева фабрика виготовляє столи, стільці, бюро та книжкові шафи, використовуючи для цього два різних види дощок, прочому фабрика має 500 м³ дощок першого виду і 1000 м³ дощок другого. Крім того задані трудові ресурси 800 людино-годин.

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

Таблиця 1

Ресурси	Витрати на один виріб
Столи	Стільці	Бюро	Книжкові шафи
Дошки першого виду, м^3
Дошки другого виду, м^3
Трудові ресурси, людино-години
Прибуток на один виріб, у.о.

Розв’язання. Припустимо, що підприємство має випустити столів, стільців, бюро, книжкових шаф. За змістом задачі , , , повинні бути невід’ємними.

На виготовлення одного стола витрачається 5 м³ деревини першого виду, а на виготовлення одного стільця – 1 м³ деревини першого виду, на виготовлення одного бюро – 4 м³, однієї книжкової шафи – 12 м³ деревини першого виду. Тоді на виготовлення столів витрачають 5 м³ цієї деревини, на виготовлення стільців - м³ деревини першого виду, на виготовлення бюро - 4 м³ деревини першого виду, на виготовлення книжкових шаф – 12 м³ деревини першого виду. Всі витрати деревини першого виду становлять і не перебільшують запаси підприємства 500 м³, а витрати деревини другого виду становлять і не перебільшують запаси підприємства 1000 м³. Витрати трудових ресурсів становлять і не перебільшують 800 людино-годин.

Загальний прибуток підприємства від виробництва меблів становить:

.

Отже, маємо математичну постановку (математичну модель) задачі:

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

Дата добавления: 2015-05-23