Простые однопроходные эвристики для решения одномерной задачи покрытия

    Федеральное агентство по образованию

    государственное образовательное учреждение высшего  профессионального образования

    Уфимский  Государственный Авиационный Технический Университет 
 
 
 
 

    Кафедра Компьютерной Математики 
 
 
 
 
 
 
 
 
 

    Пояснительная записка к курсовой работе

    на  тему:

    Простые однопроходные эвристики для  решения одномерной задачи покрытия. 
 
 
 
 
 
 
 
 
 
 
 

    Выполнил: ст. гр. МКН-327

              Подымова М.Ю.

    Проверил:  Филиппова А.С. 
 
 
 
 

    Уфа, 2008 

Содержание  пояснительной записки: 

    

1. Постановка  и математическая модель задачи 

 

2. Метод решения, структограмма или пошаговое  описание алгоритма

 
    

3. Описание  параметров программы

 
    

4. Вычислительный  эксперимент

 
    

5. Анализ  результатов

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Постановка  и математическая модель задачи 

    Постановка  одномерной задачи максимального покрытия.

       Задачи  покрытия являются разновидностью задач  упаковки, в которых условие непересечения  заготовок  заменяется на условие  пересечения друг с другом и с  границами области упаковки.

       Для проблемы одномерного максимального  покрытия имеем следующую задачу:

       Задана: длинна L покрываемого материала (формы) и имеется m исходных элементов (деталей) заданной длинны li, и в заданном количестве bi, .

       Требуется найти план покрытия максимального  количества форм исходными деталями, т.е. найти матрицу А=[ ], компоненты которой указывают число i-х предметов j-ой упаковке и максимизирующую количество N покрытых форм:

        ,     ,  ,

        ,              

        ,               .

       Эта задача была сформулирована Е.Заком на встрече  международной группы по интересам раскроя-упаковки (SICUP) в 2002 году.

       На  рисунках 1.4 и 1.5 показаны отличия между  задачей одномерного раскроя  и задачей покрытия:

       

       Рис 1.4.. Графическое представление для  задачи одномерного раскроя.

       

       Рис 1.5. Графическое представление одномерной задачи максимального покрытия. 
 
 
 
 
 
 
 

    Однопроходные простые эвристики.

    Рассмотрим  суть однопроходных простых эвристик, на примере задачи упаковки.

    Выделяют  два основных класса алгоритмов. Они  определяются порядком упаковки предметов в корзины. Он-лайн алгоритмы рассматривают предметы в заданном порядке и упаковывают их в корзину, выбираемую с помощью некоторой стратегии. Офф-лайн алгоритмы вначале упорядочивают предметы. Как правило, офф-лайн процедура сортирует предметы в порядке невозрастания их весов (длин). Для офф-лайн алгоритмов важно, чтобы задачи были статическими, он-лайн алгоритмы могул применятся, когда предметы динамически прибывают на место упаковки или имеют случайные параметры веса (длины).

    Как правило, в обоих классах используются следующие основные стратегии выбора.

• Следующий подходящий (Next-Fit, NF). Первый предмет упаковывается в корзину №1. Каждый следующий предмет упаковывается в ту же корзину, если позволяет ее остаточная емкость. В противном случае он упаковывается в новую корзину. Он-лайн версия (NF) имеет временную сложность O(m), а версия офф-лайн (Next-Fit-Decreasing, NFD) занимает O(m*logm) времени из-за необходимости сортировки предметов.

    Пример 2.4. В контейнере емкости L=100 требуется упаковать 7 предметов, веса которых заданы  вектором w=(40, 9, 21, 37, 20, 53, 17).Определить с помощью алгоритма NF необходимое количество контейнеров для размещения всех предметов.

    Определим вначале нижнюю границу  . При этом резерв (неиспользованная вместимость) равен 100*2-97=3.

    NF алгоритм. Будем укладывать предметы в заданном порядке, пользуясь стратегией «следующий подходящий». Для загрузки предметов потребуется 3 контейнера с планом загрузки ={(1;2;3) (4;5) (6;7)},

    После загрузки 1-го контейнера предметами 1,2 и 3 остается свободная емкость, равная 30. Согласно стратегии NF следующим должен укладываться 4 предмет. Его вес равен 37 и в 1-й контейнер он не войдет. Во 2-м контейнере размещается 4-й и 5-й предметы, остается свободная емкость, равная 43. Следующий 6-й предмет размещается в 3-м контейнере. Там же  размещается 7-й предмет. План загрузки ={(1;2;3) (4;5) (6;7)}. 
 
 
 
 
 
 
 
 
 

Метод решения, структограмма  или пошаговое  описание алгоритма 

    На  входе мы имеем длину формы  и длины деталей, которыми мы бу-дем покрывать формы. Далее в зависимости от выбранной эвристики мы следуем алгоритмам и покрываем форму деталями, в последовательностях определенных выбранной эвристикой. На выходе мы получаем покрытые формы. Количество форм не ограничено, главное, чтобы все детали были использованы. И для каждой эвристики у нас получатся разные списки покрытий. В процессе анализа мы выберем наиболее удачное и оптималь-ное покрытие.

    Входные данные : (W, m, ,Эвристика)  

    Выходные  данные : (N,  , )

    В зависимости от выбранной Эвристики  упорядочить или не упорядочить  длины деталей.

    Покрывать последовательно (согласно списку) деталями форму, пока длина формы не будет  перекрыта.

    Перейти к следующей форме и повторять  предыдущий шаг, пока детали не закончатся.

    Вывести результат, где отразить размещение деталей и количество используемых форм.  
 
 
 
 
 
 
 

Листинг программы . 

#pragma once

#include "resource.h"

#include "Form_d.h"

kusok *c;

kusok *b;

kusok *m; //инициализация и заполнение масcива заготовок

list<mqueue> glist;//глобальный список контейнеров

double v; 
 

namespace KA_2_4

{ 

      using namespace System;

      using namespace System::ComponentModel;

      using namespace System::Collections;

      using namespace System::Windows::Forms;

      using namespace System::Data;

      using namespace System::Drawing;

      public ref class Form1 : public System::Windows::Forms::Form

      {

      public:

            Form1(void)

            {

                  InitializeComponent();

            } 

      protected: 

            ~Form1()

            {

                  if (components)

                  {

                        delete components;

                  }

            } 

      private: System::Void Form1_Load(System::Object^  sender, System::EventArgs^  e)

                   {

                         srand(unsigned(time(NULL)));

                         list_is_ready=0;

                   } 
 

      private: System::Void button1_Click(System::Object^  sender, System::EventArgs^  e)

                   {

           list_is_ready=1;   

                         switch(evr)

                         {

                   case0:{upakovka(m);

                              break;}

                         case 1:{

                               quick1(b,num);

                               c=new kusok[num];

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

                                     c[i]=b[i];

                         for (int i=0;i<num/2;i++)

                               {

                                     b[2*i]=c[i];

                               b[2*i+1]=c[num-i-1];

                               }

                               upakovka(b);

                      break;}

                         case 2:{quick1(b,num);

                               c=new kusok[num];

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

                               { c[i]=b[i];

                               }

                               switch(num)

                               {

                               case 20:

                                     {