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

Страницы работы

Содержание работы

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

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

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

Отчет

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

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

Вариант №5

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

Группа:

Студентка:

Преподаватель: Кириллов Ю.В.

Новосибирск

2007

Цель работы: Приобрести практические навыки и опыт решения задач целочисленного линейного программирования на ЭВМ. Различать общие и частные модели ЗЦЛП, выбирать методы решения, анализировать результаты.

Условие задачи: Коммерческая фирма закупила товары четырех наименований А1, А2, А3, А4 по 10 упаковок каждого за пределами своего города. Доставку товаров предполагается осуществить собственным автофургоном за несколько рейсов. Грузоподъемность фургона составляет V кг. Вес одной упаковки товара каждого наименования равен соответственно v1, v2, v3, v4 кг, а стоимость – с1, с2, с3, с4 тыс. руб.

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

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

V

V1

V2

V3

V4

C1

C2

C3

C4

85

7

14

13

15

15

48

33

50

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

1)  Входим в режим решения ЗЦЛП в ПЭР, знакомимся с правилами работы в режиме.

2)  Вводим условие задачи по своему варианту.

Строим целевую функцию:  Z=150x1 + 480x2 + 330x3 +500x4 ® max

Ограничения:

            7x1 + 14x2 + 13x3 + 15x4 <= 85,

            X1 <=10

           X3 <=10

           x1, x2, x3, x4 >= 0 и целые

3)  Решаем задачу методом ветвей и границ:

4)  Анализируем полученное решение и строим дерево решения:

 


Найдено оптимальное решение задачи!!!

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

5)  Решаем эту же задачу методом Гомори, используя средства ПЭР (режим Линейного Программирования).

Вводим условие задачи без учета целочисленности переменных.

Решаем задачу симплекс-методом:

6)  Записываем в виде ЗЦЛП задачу о назначениях, сформированную в лабораторной работе №2, и находим оптимальный план, полученный методом ветвей и границ. Сравниваем с результатом, полученным ранее.

          3x11+4x12+2x13+9x14

Z=     5x21+10x22+7x23+14x24,                       min

          7x31+2x32+11x33+3x34

              0x41+19x42+4x43+20x44

 

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

х11121314 =1

х21222324 =1

х31323334 =1

х41424344 =1

х112131+x41 =1

х122232+x42 =1

х132333+x43 =1

х142434+x44 =1

Оптимальный план задачи о назначениях, полученный методом ветвей и границ:

Решение, полученное методом ветвей и границ, и решение, полученное в лабораторной работе №2, совпадают. Это говорит о том, что оба метода одинаково хорошо подходят для решения задачи о назначениях.

7)  Решить ту же задачу о назначениях венгерским методом.

Решение, полученное по методу ветвей и границ полностью совпадает с решением, полученным по венгерскому методу. Следовательно, этот метод также хорошо можно применять для решения задачи о назначениях, как и предыдущие.

9) Вводим условия произвольной задачи о назначениях с матрицей эффективности размером 6*8 и решаем ее дважды: по критерию максимума и по критерию минимума.

Оптимальный план задачи о назначениях по критерию максимизации:

Решим ту же задачу по критерию минимизации:

Проанализировав процесс, можно сделать вывод, что максимальное значение целевой функции = 71, минимальное значение =20.

10) Оптимальное решение является единственным.

Вывод: Мы приобрели практические навыки и опыт решения задач целочисленного линейного программирования на ЭВМ (для этого ознакомились с правилами работы в различных режимах), научились различать общие и частные модели ЗЦЛП, выбирать методы решения, анализировать результаты. Также были рассмотрены разные методы решения задачи о назначениях, которая была вновь решена методом ветвей и границ, а также венгерским методом.                   

Похожие материалы

Информация о работе