Решение задач целочис­ленного линейного программирования на ЭВМ

МО и ПО РФ Новосибирский Государственный Технический Университет Кафедра экономической информатики Лабораторная работа №3 ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ   Вариант 16 Факультет: Бизнеса Группа : Студенты:                     Преподаватель: Новосибирск 2003

Цель работы:

- приобрести практические навыки и опыт решения задач целочис­ленного линейного программирования на ЭВМ;

- различать общие и частные модели ЗЦЛП, выбирать методы реше­ния, анализировать результаты.

Условие задачи:                                                     

коммерческая фирма закупила товары четырех наименований А₁, A₂, А_з и А₄ по 10 упаковок каждого за пределами своего города. Доставку товаров предполагается осуществить собственным автофурго­ном за несколько рейсов. Грузоподъемность фургона составляет V кг. Вес одной упаковки товара каждого наименования равен соответствен­но v₁, v₂, v₃ и v₄ кг, а стоимость – с₁, с₂, с₃ и с₄ тыс. руб. Определить, какие виды товаров и в каком количестве необходимо перевезти первым рейсом, с тем, чтобы их стоимость была максималь­ной.

№	V	v1	v2	v3	v4	с1	с2	с3	с4
16	95	11	9	7	15	530	480	360	650

Исходные данные:

Порядок выполнения работы:

1.   Ознакомившись с правилами работы  ПЭРа в режиме «Целочисленное линейное программирование», приступаем к выполнению лабораторной работы №3.

2.  Вводим условия задачи №3 расчетно-графической (контроль­ной) работы (16 вариант), присваивая имя задаче «tr316», составляя при этом математическую модель данной задачи:       z =                                                                   

при ограничениях:

:

ПЭР выводит нам следующее:

ВХОДНЫЕ ДАННЫЕ, описывающие задачу  лаба3(16)

Max  +530.000X1  +480.000X2  +360.000X3  +650.000X4

При услов.

( 1) +11.0000X1  +9.00000X2  +7.00000X3  +15.0000X4  <= +95.0000

Целочисленные границы на переменные

(По умолчанию значение нижних границ - 0, а верхних границ -  32000)

 Пер. No.     Им   Тип I/C (Ц/Н)    Ниж.граница    Вер.граница

      1        X1       <I>          <0>             <10>

      2        X2       <I>          <0>             <10>

      3        X3       <I>          <0>             <10>

      4        X4       <I>          <0>             <10>

┌─────────────────────────────────────────────────────────────────┐

│   ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 1  Стр.: 1      │

╞═══════════╤════════╤══════════╦════════╤════════════╤═══════════╡

│ Ниж.гран. │Перемен.│Верх.гран ║Перемен.│  Решение   │Целев.ф-ия.│

╞═══════════╪════════╪══════════╬════════╪════════════╪═══════════╡

│  0       є│  X1    │є 10      ║  X1    │      0.000 │   530.000 │

│  0       є│  X2    │є 10      ║  X2    │     10.000 │   480.000 │

│  0       є│  X3    │є 10      ║  X3    │      0.714 │   360.000 │

│  0       є│  X4    │є 10      ║  X4    │      0.000 │   650.000 │

╞═══════════╧════════╧══════════╩════════╧════════════╧═══════════╡

│  НЕПРЕРЫВНОЕ РЕШЕНИЕ С  Ц.Ф.  (Max.) = 5057.143  ZL =-1E+20     │

└─────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────┐

│   ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 2  Стр.: 1      │

╞═══════════╤════════╤══════════╦════════╤════════════╤═══════════╡

│ Ниж.гран. │Перемен.│Верх.гран ║Перемен.│  Решение   │Целев.ф-ия.│

╞═══════════╪════════╪══════════╬════════╪════════════╪═══════════╡

│  0       є│  X1    │є 10      ║  X1    │      0.000 │   530.000 │

│  0       є│  X2    │є 10      ║  X2    │      9.778 │   480.000 │

│  1       є│  X3    │є 10      ║  X3    │      1.000 │   360.000 │

│  0       є│  X4    │є 10      ║  X4    │      0.000 │   650.000 │

╞═══════════╧════════╧══════════╩════════╧════════════╧═══════════╡

│  НЕПРЕРЫВНОЕ РЕШЕНИЕ С  Ц.Ф.  (Max.) = 5053.334  ZL =-1E+20     │

└─────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────┐

│   ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 3  Стр.: 1      │

╞═══════════╤════════╤══════════╦════════╤════════════╤═══════════╡

│ Ниж.гран. │Перемен.│Верх.гран ║Перемен.│  Решение   │Целев.ф-ия.│

╞═══════════╪════════╪══════════╬════════╪════════════╪═══════════╡

│  0       є│  X1    │є 10      ║        │            │           │

│  10      є│  X2    │є 10      ║        │            │           │

│  1       є│  X3    │є 10      ║        │            │           │

│  0       є│  X4    │є 10      ║        │            │           │

╞═══════════╧════════╧══════════╩════════╧════════════╧═══════════╡

│             Эта ветвь имеет НЕДОПУСТИМОЕ решение                │

└─────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────┐

│   ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 4  Стр.: 1      │

╞═══════════╤════════╤══════════╦════════╤════════════╤═══════════╡

│ Ниж.гран. │Перемен.│Верх.гран ║Перемен.│  Решение   │Целев.ф-ия.│

╞═══════════╪════════╪══════════╬════════╪════════════╪═══════════╡

│  0       є│  X1    │є 10      ║  X1    │      0.000 │   530.000 │

│  0       є│  X2    │є 9       ║  X2    │      9.000 │   480.000 │

│  1       є│  X3    │є 10      ║  X3    │      2.000 │   360.000 │

│  0       є│  X4    │є 10      ║  X4    │      0.000 │   650.000 │

╞═══════════╧════════╧══════════╩════════╧════════════╧═══════════╡

│ ЦЕЛОЧИСЛ. ДОПУСТИМОЕ РЕШЕНИЕ С  ЦФ (Max.) = 5040 Є ZL =-1E+20   │

└─────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────┐

│   ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 5  Стр.: 1      │

╞═══════════╤════════╤══════════╦════════╤════════════╤═══════════╡

│ Ниж.гран. │Перемен.│Верх.гран ║Перемен.│  Решение   │Целев.ф-ия.│

╞═══════════╪════════╪══════════╬════════╪════════════╪═══════════╡

│  0       є│  X1    │є 10      ║  X1    │      0.455 │   530.000 │

│  0       є│  X2    │є 10      ║  X2    │     10.000 │   480.000 │

│  0       є│  X3    │є 0       ║  X3    │      0.000 │   360.000 │

│  0       є│  X4    │є 10      ║  X4    │      0.000 │   650.000 │

╞═══════════╧════════╧══════════╩════════╧════════════╧═══════════╡

│   НЕПРЕРЫВНОЕ РЕШЕНИЕ С  Ц.Ф.  (Max.) = 5040.909  ZL = 5040     │

└─────────────────────────────────────────────────────────────────┘