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

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

min (max) f(x₁ ,x₂ ,…,x_n);

g_j (x₁ ,x₂ ,…,x_n) {≤¸=¸≥} x_j ≥0, j= 1, m

x_j — целые неотрицательные < п'> .

Если множество индексов <п'> = <п > – {1, 2, ... , п} , то задачу называют полностью целочисленной, если <n'> <n>,то частично целочисленной.

Существуют различные методы решения задач дискретного программирования (дискретной оптимизации). Наиболее часто используемым методом является метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета Ехсеl.

Дискретная оптимизация средствами Ехсеl проводится аналогично решению соответствующих непрерывных задач. Основное отличие заключается во вводе при оформлении диалогового окна Поиск решения требования целочисленности соответствующих переменных (при этом в режиме Параметры устанавливается тип задачи - линейная или нелинейная).

Исходя из требования целочисленности в случае дискретной оптимизации возможен вызов только одного Отчета по результатам.

Достаточно часто при моделировании экономических процессов используется особый случай дискретности задачи - булевость переменных, т.е. переменные могут принимать значения 0 или 1. Характерным примером этого случая является задача о назначениях (приводится в качестве примера задачи дискретной оптимизации и для иллюстрации механизма учета в Excel булевости переменных).

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

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

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

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

max f(x₁, x₂, x₃, x₄) =100x₁+80x₂+40x₃+30x₄, 20x₁+15x₂+20x₃+14x₄ ≤ 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 у. е., и грузоподъёмность будет использована полностью.