Пример задачи целочисленного линейного программирования

Задача. Организация арендует баржу грузоподъёмностью 200 т. На этой барже предполагается перевозить груз 4 типов. Вес и стоимость единицы груза соответственно равны 20, 15, 20, 14 и 100, 80, 40, 30. Необходимо погрузить на баржу груз максимальной стоимости.

Экономико-математическая модель:

Введём необходимые обозначения: пусть x_j (j =1,2,3,4) – число предметов j -го типа, которое следует погрузить на баржу. Тогда ЭММ задачи о подборе для баржи допустимого груза максимальной стоимости запишется следующим образом:

max f (x ₁, x ₂, x ₃, x ₄) =100 x ₁+80 x ₂+40 x ₃+30 x ₄, 20 x ₁+15 x ₂+20 x ₃+14 x ₄ ≤ 200, x_j (j =1, 2, 3, 4) – целые неотрицательные.

Решение.

Необходимо последовательно выполнить следующие операции:

1. Создать текстовую форму-таблицу для ввода условий задачи и ввести исходные данные:

2. Ввести зависимость для целевой функции:

· курсор в ячейку F4;

· кнопка Мастер функции;

· на экране появится диалоговое окно Мастер функций – шаг 1 из 2.

· выбрать на категорию Математические;

· выбрать функцию СУММПРОИЗВ;

· в строку Массив 1 ввести B$3:E$3;

· в строку Массив 2 ввести B4:E4;

· кнопка ОК.

3. Ввести зависимость для ограничений:

· скопировать полученную формулу в ячейку F8.

В строке Меню указатель мыши на Сервис. В развёрнутом меню команда Поиск решения. Появляется диалоговое окно Поиск решения.

4. Назначим целевую функцию (установим целевую ячейку):

· курсор в строку Установить целевую ячейку;

· введем адрес ячейки $F$4;

· введем направление целевой функции в зависимости от условия задачи – Максимальному значению;

· курсор в строку Изменяя ячейки;

· введем адреса искомых переменных $B$3:$E$3.

5. Введите ограничения:

· кнопка Добавить. Появляется диалоговое окно Добавление ограничения;

· в строке Ссылка на ячейку введем (или укажем на листе) адрес $F$8;

· выберем знак ограничения <=;

· в строке Ограничение введем адрес $H$8;

· кнопка Добавить

· в строке Ссылка на ячейку введем (или укажем на листе) адрес $B$3:$E$3;

· выберем значение цел

 

· кнопка ОК.

 

На экране появится диалоговое окно Поиск решения с введёнными условиями.

6. Введем параметры для решения задачи:

· кнопка Параметры.

· на экране диалоговое окно Параметры поиска решения;

· установим флажки:

ü Линейная модель (это обеспечит применение симплекс-метода)

ü Неотрицательные значения;

· кнопка ОК.

· на экране появится диалоговое окно Поиск решения;

· кнопка Выполнить.

Появится диалоговое окно Результаты поиска решения.

· выберем Сохранить найденное решение

· кнопка ОК.

 

Таким образом, рекомендуемое управленческое решение с позиций принятого критерия оптимизации – следует погрузить 1 предмет первого типа и 12 предметов второго типа. В этом случае стоимость груза составит 1060 у. е., и грузоподъёмность будет использована полностью.