Решение задач целочисленного линейного программирования на ЭВМ (доставка товаров коммерческой фирмой)

Министерство образования Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра Экономической Информатики

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

Целочисленное линейное программирование

Факультет: Бизнеса

Группа:

Студент:

Преподаватель:

Новосибирск 2006

Цель работы

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

- различать общие и частные модели PWKG? Выбирать методы решения, анализировать результаты.

Задача к лабораторной работе:

Коммерческая фирма закупила товары четырех наименований А1, A2, А3 и А4 по 10 упаковок каждого за пределами своего города. Доставку товаров предполагается осуществить собственным автофурго­ном за несколько рейсов. Грузоподъемность фургона составляет V кг. Вес одной упаковки товара каждого наименования равен соответствен­но Vi, V2, уз и V4 кг, а стоимость – C1, C2, C3 и С4 тыс. руб.

Определить, какие виды товаров и в каком количестве необходимо перевезти первым рейсом, с тем, чтобы их стоимость была максималь­ной

Числовые данные:

V	V1	V2	V3	V4	C1	C2	C3	C4
46	8	5	7	6	500	450	470	510

I.  Модель задачи:

II.  Решение методом ветвей и границ:

+-----------------------------------------------------------------+

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

¦-----------------------------------------------------------------¦

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

¦-----------+--------+----------+--------+------------+-----------¦

¦  0       є¦  X1    ¦є 10      ¦  X1    ¦      0.000 ¦   500.000 ¦

¦  0       є¦  X2    ¦є 10      ¦  X2    ¦      9.200 ¦   450.000 ¦

¦  0       є¦  X3    ¦є 10      ¦  X3    ¦      0.000 ¦   470.000 ¦

¦  0       є¦  X4    ¦є 10      ¦  X4    ¦      0.000 ¦   510.000 ¦

¦-----------------------------------------------------------------¦

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

+-----------------------------------------------------------------+

+-----------------------------------------------------------------+

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

¦-----------------------------------------------------------------¦

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

¦-----------+--------+----------+--------+------------+-----------¦

¦  0       є¦  X1    ¦є 10      ¦        ¦            ¦           ¦

¦  10      є¦  X2    ¦є 10      ¦        ¦            ¦           ¦

¦  0       є¦  X3    ¦є 10      ¦        ¦            ¦           ¦

¦  0       є¦  X4    ¦є 10      ¦        ¦            ¦           ¦

¦-----------------------------------------------------------------¦

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

+-----------------------------------------------------------------+

+-----------------------------------------------------------------+

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

¦-----------------------------------------------------------------¦

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

¦-----------+--------+----------+--------+------------+-----------¦

¦  0       є¦  X1    ¦є 10      ¦  X1    ¦      0.000 ¦   500.000 ¦

¦  0       є¦  X2    ¦є 9       ¦  X2    ¦      9.000 ¦   450.000 ¦

¦  0       є¦  X3    ¦є 10      ¦  X3    ¦      0.000 ¦   470.000 ¦

¦  0       є¦  X4    ¦є 10      ¦  X4    ¦      0.167 ¦   510.000 ¦

¦-----------------------------------------------------------------¦

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

+-----------------------------------------------------------------+

+-----------------------------------------------------------------+

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

¦-----------------------------------------------------------------¦

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

¦-----------+--------+----------+--------+------------+-----------¦

¦  0       є¦  X1    ¦є 10      ¦  X1    ¦      0.000 ¦   500.000 ¦

¦  0       є¦  X2    ¦є 9       ¦  X2    ¦      8.000 ¦   450.000 ¦

¦  0       є¦  X3    ¦є 10      ¦  X3    ¦      0.000 ¦   470.000 ¦

¦  1       є¦  X4    ¦є 10      ¦  X4    ¦      1.000 ¦   510.000 ¦

¦-----------------------------------------------------------------¦

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

+-----------------------------------------------------------------+

+-----------------------------------------------------------------+

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

¦-----------------------------------------------------------------¦

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

¦-----------+--------+----------+--------+------------+-----------¦

¦  0       є¦  X1    ¦є 10      ¦  X1    ¦      0.000 ¦   500.000 ¦

¦  0       є¦  X2    ¦є 9       ¦  X2    ¦      9.000 ¦   450.000 ¦

¦  0       є¦  X3    ¦є 10      ¦  X3    ¦      0.143 ¦   470.000 ¦

¦  0       є¦  X4    ¦є 0       ¦  X4    ¦      0.000 ¦   510.000 ¦

¦-----------------------------------------------------------------¦

¦   НЕПРЕРЫВНОЕ РЕШЕНИЕ С  Ц.Ф.  (Max.) = 4117.143  ZL = 4110     ¦

+-----------------------------------------------------------------+

+-----------------------------------------------------------------+

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

¦-----------------------------------------------------------------¦

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

¦-----------+--------+----------+--------+------------+-----------¦

¦  0       є¦  X1    ¦є 10      ¦  X1    ¦      0.000 ¦   500.000 ¦

¦  0       є¦  X2    ¦є 9       ¦  X2    ¦      7.800 ¦   450.000 ¦

¦  1       є¦  X3    ¦є 10      ¦  X3    ¦      1.000 ¦   470.000 ¦

¦  0       є¦  X4    ¦є 0       ¦  X4    ¦      0.000 ¦   510.000 ¦