О целочисленной оптимизации в экономических задачах

 

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

Актуальность данного исследования обусловлена тем, что на практике часто встречаются проекты, которые нельзя реализовать по частям. Кроме того, сами объекты производства или инвестирования могут не подлежать дроблению (например, здания, персонал и др.). В этих случаях целесообразно воспользоваться методологией целочисленной оптимизации.

Анализ достижений и публикаций. Проблемам целочисленности оптимизации уделяли внимание такие учёные как В.В.Леонтьев, Л.В.Канторович, И.И.Дикин, А.М.Семахин и др. Из зарубежных учёных наиболее известен Р.Гомори, который в 1958 г. предложил метод отсечения плоскостей [1, с. 132-147], [2, гл. 9]. Современные исследователи [3] тоже уделяют внимание проблемам целочисленной оптимизации.

Основная часть. Рассмотрим задачи целочисленности линейной оптимизации (ЦЛО), когда целевая функция и ограничения являются линейными. Математическая модель ЦЛО такая же, как и задача линейной оптимизации, но с дополнительным требованием целочисленности всех или части неизвестных. Если требование целочисленности распространяется на часть неизвестных величин задачи, то такая задача называется частично целочисленной.

Запишем математическую модель задачи ЦЛО. Требуется найти экстремальное значение целевой функции

при ограничениях

и целые для всех .

Задачи целочисленной оптимизации решаются методом Гомори, методом ветвей и границ, которые реализованы при помощи информационных технологий. Рассмотрим вышеперечисленные методы.

Метод Гомори основан на применении симплекс-метода и метода отсечения. Сначала находится оптимальное решение задачи ЦЛО симплекс-методом, и если целочисленное решение получено, то цель достигнута. Если же оптимальное решение не является целочисленным, то в условия задачи вводится дополнительное ограничение, которое отсекает от области допустимых решений полученное решение и не отсекает от неё ни одной точки с целочисленными координатами. Далее симплекс-методом решается расширенная задача. Если новое решение не будет целочисленным, то вводится ещё одно дополнительное ограничение, и процесс повторяется до тех пор, пока не будет найдено оптимальное целочисленное решение, или не будет установлено, что его не существует. Геометрическая иллюстрация метода Гомори осуществляется с помощью графического поля, на которое нанесена целочисленная сетка.

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

Особый интерес представляет собой способ решения задачи целочисленной оптимизации средствами Excel. Приведём пример такой задачи и решим её при помощи информационных технологий.

Морское судно грузоподъёмностью 20 тыс. т. и вместимостью 28 тыс. м³ может быть использовано для перевозки пяти видов груза. Данные о массе, объёме и стоимости единицы груза приведены в табл. 1.

Таблица 1

Данные задачи

Параметры единицы груза	Номер груза
Масса, т
Объём, м^3
Стоимость, тыс. руб.

 

Требуется определить, сколько единиц груза каждого вида следует загрузить на судно, чтобы суммарная стоимость груза была максимальной и выполнялись ограничения по вместимости и грузоподъёмности судна.

Составим математическую модель данной задачи:

и целые для всех .

Решение данной задачи осуществляется командой «Поиск решения» из меню «Сервис». Далее в форму представления данных вносят всё необходимое [1, с. 142-145]. Закончив ввод ограничений, командой «Добавить» вводят условия целочисленности. Для этого в диалоговом окне «Добавление ограничения» вводят в окно ссылку на ячейку адреса, где должны быть изменяемые значения неизвестных.

Таким образом, проведя вычисление при помощи Excel, получим оптимальный план и экстремальное значение целевой функции:

, (тыс. руб.).

Подведение итогов. В данном исследовании проведен анализ целочисленной оптимизации в экономических задачах, рассмотрены основные методы решения данных задач – метод Гомори, метод ветвей и границ, использование программного обеспечения Excel, обоснована необходимость применения каждого из методов. Таким образом, можно сделать вывод, о том, что задачи целочисленной оптимизации имеют практическую направленность, их решение обеспечивает максимизацию или минимизацию при условии целочисленности переменных.

 

Литература:

5. Костевич Л.С. Математическое программирование: информационные технологии оптимальных решений: [учеб. пособие] / Л.С.Костевич. – Мн.: Новое знание, 2003. – 424 с.: ил. – Библиогр.: с. 419. – ISBN 985-6516-83-8.

6. Таха Х.А. Введение в исследование операций, 7-е издание.: Пер. с англ. / Х.А.Таха. – М.: Издательский дом «Вильямс», 2005. – 912 с.: ил. – ISBN 5-8459-0740-3 (рус.).

7. Полшков Ю.Н. О современных подходах экономико-математического моделирования в маркетинге // Вiсник Донецького національного унiверситету. Серiя В. Економiка i право. Спецвипуск, том 2. – Донецьк: ДонНУ, 2012. – С. 199-207.

 

 

Полшков Ю.Н.

Донецкий национальный университет