У даному випадку шуканою є точка Е(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;