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

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 у. е., и грузоподъёмность будет использована полностью.

Задачи для самостоятельного решения

1. Задача об оптимальном использовании ограниченных ресурсов. На участок строящейся дороги необходимо вывезти 20 000 м³ каменных материалов. В районе строительства имеются три карьера с запасами 8000м³, 9000 м³ и 10000 м³. Для погрузки материалов используются экскаваторы, имеющие производительность 250 м³/смену в карьерах А, Б и 500 м³/смену в карьере В. Эти карьеры обеспечивают каменными материалами также ряд других строящихся объектов. На погрузку материалов для рассматриваемого участка выделен для экскаваторов общий лимит 60 машино/смен с правом использовать его по усмотрению строителей. Транспортные затраты на перевозку материалов характеризуются следующими показателями: на перевозку 1000 м³ материалов из карьера А требуется 100 машино/смен, из карьера Б – 135 машино/смен, из карьера B – 170 машино/смен.

Требуется составить оптимальный план перевозок, обеспечивающий минимальные транспортные затраты.

2. Предлагается 5 инвестиционных проектов, тщательная экономическая экспертиза которых позволяет получить для каждого из проектов достаточно убедительные экономические оценки ожидаемого эффекта от их реализации 80; 50; 75; 40; 45 усл. ед. и необходимых капиталовложений 110; 60; 80; 15; 30 усл. ед. Общий объем возможных инвестиций ограничен величиной 200 усл. ед. Необходимо так распорядиться имеющимися финансовыми ресурсами, чтобы максимизировать суммарный эффект от инвестиций.

3. Задача о рациональном раскрое строительных материалов. Часть заемных оборотных средств предприятия иммобилизована в запасы пиломатериалов: на складе имеется партия бруса, содержащая 300 штук длиной 7,5 м каждый и партия бруса, содержащая 500 штук длиной 5 м каждый. Из этого материала можно изготовить оконные блоки, в каждый из которых входит две детали по 2,5 м и три детали длиной 2 м каждая. Как оптимально использовать заемные средства, если предположить, что спрос на оконные рамы неограничен?