Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

(11)

при умові, що сумарний об'єм закуповуваних партій не перевищить місткості складу

(12)

Очевидно,

(13)

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

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

Позначимо через, x_j активну потужність, яка генерується на _j-й електростанції. Потужності x_j лежать у межах, які визначаються технічними умовами: . Крім того, повинно виконуватись умова балансу потужностей, тобто загальна потужність, що генерується, повинна відповідати потужності Р, яка споживається, з урахуванням загальних втрат у лініях передач:

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

(14)

при умовах

(15)

(16)

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

В якості наступного наближення можна розглядати задачу, в якій π є білінійною функцією , де параметри управління x_y означають кількість активної потужності, яка передається з _j-й електростанції у _i-й вузол.

Очевидно, що в цієї нової моделі умови будуть містити нелінійності (π (x_y.) в рівнянні балансу).

Задача про розміщення. Ця простіша задача про розміщення є прикладом багатоекстремальної задачі.

Є т можливих пунктів виробництва, причому відома для кожного i-го пункту залежність вартості виробництва f_i від об'єму виробництва x_i (передбачається, що у вартість виробництва включені капітальні витрати). Дані пунктів споживання із заданим об'ємом споживання b_j у кожному пункті. Нарешті, задана матриця транспортних витрат ( ) ( - вартість перевезення одиниці продукції з i-го пункту виробництва в _j-й пункт споживання). Необхідно знайти такі об'єми виробництва , які мінімізують сумарні витрати; інакше кажучи, шукається

(17)

при умовах

(18)

(19)

Оскільки собівартість одиниці продукції звичайно спадає при збільшені об'єму виробництва, то функції f_i (y_i), як правило, монотонно зростають і опуклі вгору. Множина значень x_ij, що задовольняє обмеження задачі, утворює опуклий многокутник, вершини якого є точками локальних мінімумів функції l(x_ij) (рис. 1).

Рис. 1. Звідси й назва подібних задач - багатоекстремальні.

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

2. Дві стандартні форми задач лінійного програмування

Загальна форма задачі лінійного програмування (3.1) - (3.6) не придатна для побудови досить простих і ефективних методів розв'язування її, причиною чого е неоднорідність системи умов (3.2) -(3.6). Тому, як правило, задачу зводять до стандартної форми.

В залежності від методів, які застосовуються, розрізняють дві стандартні форми:

основна задача лінійного програмування з обмеженнями-рівностями або перша стандартна форма;

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

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

(21)

(22)

(23)

Або у короткому запису

(21а)

(22а)

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

Тут — вектор-стовпець змінних, — вектор-стовпець вільних членів, А — матриця системи основних обмежень, - вектор-стовпець матриці А; — вектор-рядок коефіцієнтів цільової функції, - вектор-рядок матриці А.

Скалярно-векторна форма:

(216)

(22б)

(23б)

Матрична форма:

(21в)

(22в)

(23в)

Векторна форма:

(21г)

(22г)

(23г)

Лема 1. Будь-яку задачу лінійного програмування у загальній формі можна звести до першої стандартної форми.

Доведення. Покажемо, що будь-яку нерівність, введенням додаткової невідомої можна звести до рівності. Дійсно, нехай деяке обмеження має вигляд

Перепишемо його таким чином:

Введемо позначення

За побудовою є невід'ємною величиною. Крім того останнє

співвідношення є рівняння відносно невідомих :

Отже ми прийшли до рівності еквівалентній вихідної нерівності.

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

Наступний крок полягає в зведені до однорідної системи обмежень на знак. Умови недодатності (3.6) легко перетворюються в умови невід'ємності за допомогою заміни відповідних змінних .

Складніше позбутися змінних, на знак яких обмежень не накладено. Цього можна досягти двома способами.

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

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

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

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

(24)

Визначивши оптимальні значення та , можемо знайти за (24) і оптимальне значення відповідних

Приклад 1. Звести до першої стандартної форми таку задачу лінійного програмування:

Розв'язання. Введенням однієї додаткової змінної та заміною зводимо задачу до вигляду

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

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

№ рядка
0	-6	3	4	-5	0	0
1	2	-6	-2		0	12
2	3	1	-2	1	0	6
3	1	-1	-4	2	1	8

Вибравши = 1 ключовим елементом, переходимо до нової таблиці.

№ рядка
0	4	-27	-6	0	0	60
1	2	-6	_2	1	0	12
2	1	7	0	0	0	-6
3	-3	11	0	0	1	-16

Виписуючи окремо 1-й рядок (виразивши з нього, ) і замінивши , дістаємо першу стандартну форму задачі

Характеристики

Список файлов курсовой работы