Задача о рюкзаке

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)»  

[pic 1]

Кафедра " Прикладная математика"

Отчет по лабораторной работе

по дисциплине «Дискретная оптимизация»

«Задача о рюкзаке»

                                                                                  Подготовила:

ст. гр. УПМ-311 Пономарева К.В.

                                                                               Проверила:

                                                                                        Иванова Александра Петровна

Москва, 2018

        Постановка задачи :

n – количество предметов

сj ≥ 0– ценность предмета  j = 1..n

аj ≥ 0 – вес предмета  j = 1..n ,   аj < R  – вместимость рюкзака[pic 2]

Необходимо сложить в рюкзак предметы, не превышая общий вес, максимизировав стоимость. Целевая функция:  [pic 3]

        [pic 4]

Ограничение:  [pic 5]

        [pic 6]

Пример.

6x1+5x2+2x3+3x4+4x5+5x6+4x7+8x8+7x9+3x10[pic 7]

2x1+2x2+2x3+x4+2x5+2x6+2x7+3x8+3x9+x10≤10

Результат работы программы:

[pic 8]

Верхняя граница, полученная с помощью алгоритма Данцига не целая, что легко исправить, сделав переменную F целочисленного типа (double → int).

Для исследования поведения алгоритмов при большом количестве предметов, построим графики.

n – количество предметов в задаче,

f1 – среднее значение  оптимума, полученного методом Данцига,

f2 – среднее значение  оптимума, полученного назначением единиц по ценности, (выборка  состоит из шести значений)

[pic 9]

Код программы:

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#define n 85

using namespace std;

double f[n], f1[n];//целевая функция

int F, G;//для получения целого числа в результате алг.Данцига

//double Fc[] = { 6, 5, 2, 3, 4, 5, 4, 8, 7, 3 }, Gc[] = { 2, 2, 2, 1, 2, 2, 2, 3, 3, 1 };

double lambda[n], l[n];

double y[n];

void sortBubble(double *a){

        for (int i = 0; i < n - 1; i++) {

                for (int j = 0; j < n - i - 1; j++) {

                        if (a[j] < a[j + 1]) {

                                double b = a[j + 1]; //change for elements

                                a[j + 1] = a[j];

                                a[j] = b;

                        }

                }

        }

}

void Danzig(double *g1){

        double temp; temp = g1[n + 1];

        cout << "\n Алгоритм Данцига\n\n";

        sortBubble(l); for (int i = 0; i < n; i++)cout << l[i] << "  "; cout << endl << endl;