Лінійна та нелінійна оптимізація. Побудова оптимальних планів

Размещено на http://www.allbest.ru/

1. Графічним методом визначити оптимальні плани задач лінійної оптимізації

Розв'язок:

1. Побудуємо багатокутник розв'язків системи обмежень. Він є перетином 5 напівплощин , , , , :

Побудуємо вектор нормалі .

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

В даному випадку це точка А - точка перетину прямих і . Її координати знайдемо з системи рівнянь:

Значення знайдемо, підставивши в форму координати т. А:

Відповідь:

оптимізація план симплексний двоїстий



2. Побудувати першу симплексну таблицю

Розв'язок:

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

Зведемо систему обмежень до канонічної форми:

Матриця коефіцієнтів системи рівнянь має вигляд:

Розв'яжемо систему рівнянь відносно базисних змінних . Вважаючи, що вільні змінні дорівнюють 0, одержимо перший опорний план: .

Базис	B	x1	x2	x3	x4	x5
x3	-6	-3	-1	1	0	0
x4	-15	-3	-5	0	1	0
x5	6	1	1	0	0	1
F(X0)	0	-8	-4	0	0	0

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

.

Мінімальне значення відповідає 2-му стовпцю, тобто змінну необхідно ввести в базис.

Базис	B	x1	x2	x3	x4	x5
x3	-6	-3	-1	1	0	0
x4	-15	-3	-5	0	1	0
x5	6	1	1	0	0	1
	0	-8	-4	0	0	0
	0			-	-	-

Виконуємо перетворення симплексної таблиці методом Жордана-Гаусса. Одержимо:

Базис	B	x1	x2	x3	x4	x5
x3	-3	-12/5	0	1	-1/5	0
x2	3	3/5	1	0	-1/5	0
x5	3	2/5	0	0	1/5	1
	12	-28/5	0	0	-4/5	0

Одержаний план є псевдопланом, тому здійснивши аналогічні перетворення, одержимо:

Базис	B	x1	x2	x3	x4	x5
x1	5/4	1	0	-5/12	1/12	0
x2	9/4	0	1	1/4	-1/4	0
x5	5/2	0	0	1/6	1/6	1
	19	0	0	-7/3	-1/3	0

В базисному стовпчику всі елементи додатні, тому можна переходити до основного алгоритму симплекс-методу.

Базис	B	x1	x2	x3	x4	x5
x1	5/4	1	0	-5/12	1/12	0
x2	9/4	0	1	1/4	-1/4	0
x5	5/2	0	0	1/6	1/6	1
	19	0	0	-7/3	-1/3	0

3. Побудувати двоїсту задачу до поставленої і визначити оптимальний план прямої та двоїстої задач

Розв'язок:

Так як пряма задача на знаходження максимуму цільової функції, то всі обмеження повинні бути або зі знаком "=", або зі знаком "?". Помножимо обидві частини кожної нерівності системи обмежень на "-1". Одержимо:

Двоїста задача утворюється з прямої задачі за такими правилами:

Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

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

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

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

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

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

Отже, за наведеними правилами побудуємо двоїсту задачу:

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

Розв'яжемо пряму задачу. Зведемо систему обмежень до канонічної форми:

Розв'яжемо систему рівнянь відносно базисних змінних . Вважаючи, що вільні змінні дорівнюють 0, одержимо перший опорний план:

Базис	B	x1	x2	x3	x4	x5
x3	-9	-3	-1	1	0	0
x4	-8	-1	-2	0	1	0
x5	-12	-1	-6	0	0	1
	0	-8	-4	0	0	0

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



Ітерація	Базис	B	x1	x2	x3	x4	x5
1	x3	-9	-3	-1	1	0	0
	x4	-8	-1	-2	0	1	0
	x5	-12	-1	-6	0	0	1
		0	-8	-4	0	0	0
					-	-	-
2	x3	-7	-17/6	0	1	0	-1/6
	x4	-4	-2/3	0	0	1	-1/3
	x2	2	1/6	1	0	0	-1/6
		8	-22/3	0	0	0	-2/3
3	x1	42/17	1	0	-6/17	0	1/17
	x4	-40/17	0	0	-4/17	1	-5/17
	x2	27/17	0	1	1/17	0	-3/17
		444/17	0	0	-44/17	0	-4/17
4	x1	2	1	0	-2/5	1/5	0
	x5	8	0	0	4/5	-17/5	1
	x2	3	0	1	1/5	-3/5	0
		28	0	0	-12/5	-4/5	0

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

Ітерація	Базис	B	x1	x2	x3	x4	x5
1	x1	2	1	0	-2/5	1/5	0
	x5	8	0	0	4/5	-17/5	1
	x2	3	0	1	1/5	-3/5	0
		28	0	0	-12/5	-4/5	0
2	x1	6	1	0	0	-3/2	1/2
	x3	10	0	0	1	-17/4	5/4
	x2	1	0	1	0	1/4	-1/4
		52	0	0	0	-11	3
3	x1	12	1	6	0	0	-1
	x3	27	0	17	1	0	-3
	x4	4	0	4	0	1	-1
		96	0	44	0	0	-8

Так як в останній таблиці наявні вектори, що складаються тільки з від'ємних елементів, то як основна задача, так і двоїста, розв'язків не мають.

Відповідь: основна і двоїста задачі розв'язків не мають.

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

Розв'язання.

Перевіримо, чи виконується для транспортної задачі умова балансу:

,

Отже, транспортна задача є закритою.

Методом мінімальної вартості знайдемо початковий опорний план транспортної задачі. У результаті одержимо таблицю:

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

(одиниць вартості).

Оскільки m=3, n=4, m+n-1=6, а заповнених клітинок у таблиці - 6, то опорний план є невиродженим.

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

Визначимо потенціали u_i і v_j для кожного рядка і стовпчика таблиці планування. Для цього складемо систему рівнянь u_i+v_j=с_ij для заповнених клітинок таблиці планування, поклавши . Перевіримо виконання умови оптимальності для незаповнених клітинок. Для цього обчислимо величини Д_ij =u_i+v_j-с_ij:

Оскільки для незаповнених клітинок усі Д_ij ?0, то знайдений опорний план є оптимальним.

Отже, розв'язок заданої транспортної задачі є таким:

.

При цьому (од. варт.).

Відповідь:

, од. варт.

5. Розв'язати задачу нелінійної оптимізації

За добу два заводи випускають n виробів. Витрати на виробництво х₁ виробів першим заводом дорівнюють f₁ (x₁) у.г.о., а витрати на виробництво х₂ виробів другим заводом - f₂ (x₂) у.г.о. Визначити, скільки виробів повинен виготовити кожний завод, щоб загальні витрати на їх виробництво були мінімальними

n = 4000,

f1 (x1) = х12 + 2 х1

f2 (x2) = 3 х22 + 4 х2

Розв'язок:

Цільова функція - загальні витрати на виробництво обох виробів.

Задача має обмеження по кількості випущених виробів: .

Розв'яжемо задачу методом множників Лагранжа. Складемо допоміжну функцію Лагранжа:

Необхідною умовою екстремуму функції Лагранжу є рівність 0 її частинних похідних. Маємо:

;

;

.

Розв'язуючи систему, одержимо:

З'ясуємо характер екстремуму в цій точці:

; ;

Так як та , то в точці маємо мінімум.

Значення цільової функції в цій точці:

(у.г.о.).

Якщо кількість випущених виробів повинна бути цілим числом, то можливі варіанти:

або .

Знайдемо значення функції для цих значень змінних:

;

.

Таким чином, .

Відповідь: у. г. о.

Література

1. Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2005. - 407 с.

2. М.С.Красс, Б.П.Чупрынов. Математика для экономистов. - М.: Питер, 2004. - 464 с.

3. Вивальнюк Л.М. Елементи лінійного програмування. К.: „Вища школа”, 1975, с. 191.

4. Ляшенко И.Н. (ред.) Линейное и нелинейное программирование. К.: „Вища школа”, 1975, с. 371.

5. Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. -- М.: Издательский дом "Вильямс", 2005. -- 912 с: ил.

Размещено на Allbest.ru

...