Смекни!
smekni.com

Методи розв’язування одновимірних та багатовимірних нелінійних оптимізаційних задач та задач лінійного цілочислового програмування (стр. 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;