Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування (стр. 8 из 9)

У даному випадку шуканою є точка Е(2;3), у якій цільова функція приймає максимальне значення

. Отже, координати точки Е визначають оптимальний план задачі 1 — 4.

б) методом Гоморі:

Для рішення задачі цілочислового програмування методом Гоморі спочатку визначимо симплекс-методом оптимальний план задачі 1 —3 без умови цілочисельностісті змінних:

і	Базис	Сб	В	4	1	0	0
				А1	А2	А3	А4
1	А3	0	9	3	1	1	0
2	А4	0	6	3	-2	0	1
3	0	- 4	-1	0	0
1	А3	0	3	0	3	1	-1
2	А1	4	2	1	-2/3	0	1/3
3	8	0	-11/3	0	4/3
1	А2	1	1	0	1	1/3	-1/3
2	А1	4	8/3	1	0	2/9	1/9
3	35/3	0	0	11/9	1/9

Тобто оптимальний план буде мати вигляд:

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

Умову 5 записуємо в канонічній формі:

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

і	Базис	Сб	В	4	1	0	0	0
				А1	А2	А3	А4	А5
1	А2	1	1	0	1	1/3	-1/3	0
2	А1	4	8/3	1	0	2/9	1/9	0
3	А5	0	-6	0	0	-2	-1	1
4	35/3	0	0	11/9	0	0
1	А2	1	3	0	1	1	0	-1/3
2	А1	4	2	1	0	0	0	1/9
3	А4	0	6	0	0	2	1	-1
4	11	0	0	1	0	1/9

З останньої симплекс-таблиці видно, що вихідна задача цілочислового програмування має оптимальний план Х* = (2; 3). При цьому плані значення цільової функції дорівнює:

.

в ) методом Ленг і Дойг

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

, при цьому .

Оскільки оптимальне рішення задачі лінійного програмування 1-3 не задовольняє умові цілочисельності, метод Ленг і Дойг заміняє простір рішень задачі лінійного програмування так, що в кінцевому результаті отримуємо рішення задачі цілочислового лінійного програмування. Для цього спочатку обираємо змінну, значення якої не є цілочисловим, тобто

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

а) задача 1:

б) задача 2:

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

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

виразимо через небазисні невідомі:

Тепер нове додаткове обмеження

запишемо в канонічній формі і допишемо його до останньої симплекс-таблиці задачі 1-3:

Отже за допомогою двоїстого симплекс-методу можемо розв’язати задачу 1:

і	Базис	Сб	В	4	1	0	0	0
				А1	А2	А3	А4	А5
1	А2	1	1	0	1	1/3	-1/3	0
2	А1	4	8/3	1	0	2/9	1/9	0
3	А5	0	-2/3	0	0	-2/9	-1/9	1
4	35/3	0	0	11/9	0	0
1	А2	1	3	0	1	1	0	-3
2	А1	4	2	1	0	0	0	1
3	А4	0	6	0	0	2	1	-9
4	11	0	0	1	0	1

Оптимальним розв’язком задачі 1 буде

, а максимальне значення цільової функції відповідно - . Оптимальне рішення задачі 1 задовольняє умову 5, тобто умову цілочисленості.

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

являється нижньою границею максимального значення цільової функції вихідної задачі 1-4.

При значенні нижньої границі

розглянемо задачу 2. Аналогічно до задачі 1 маємо:

і	Базис	Сб	В	4	1	0	0	0
				А1	А2	А3	А4	А6
1	А2	1	1	0	1	1/3	-1/3	0
2	А1	4	8/3	1	0	2/9	1/9	0
3	А5	0	-1/3	0	0	2/9	1/9	1
4	35/3	0	0	11/9	0	0

Оскільки для b=-1/3 в рядку, що йому відповідає немає від’ємних чисел, то задача 2 розв’язку не має.

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

, при цьому значення цільової функції .

Як бачимо, розв’язки, отримані трьома способами однакові.

6. Вихідний код програми

Нижче приведемо код програми для знаходження мінімуму фіункції за допомогою методу золотого перерізу і методу Фібоначчі, реалізований в С++. Результат виконання програми виводить в окремий текстовий документ Solution.txt.

· Метод золотого перерізу

// zoloto.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

#include <cmath>

#include <fstream>

using namespace std;

double g[5]={0};

double a,b;

double E=0;

void Inputkoef()

{

for (int i=0;i<5;i++)

{

cout<<"Enter a value a["<<i+1<<"] : ";

cin>>g[i];

}

}

void Inputotrez()

{

cout<<"Enter the lower limit segment a=";

cin>>a;

cout<<"Enter the upper limit of the interval b=";

cin>>b;

cout<<"enter the calculation accuracy E=";

cin>>E;

}

double f(double x)

{

return (g[0]*pow(x,4)+g[1]*pow(x,3)+g[2]*pow(x,2)+g[3]*x+g[4]);

}

double f(double);

ofstream Out;

int main(int argc, char* argv[])

{

cout<<"function has the form: a1*x^4+a2*x^3+a3*x^2+a4*x+a5->min"<<endl;