|
|
УДК 330.4 : 681.3
З-34
ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО
ПРОГРАММИРОВАНИЯ
Зарипова З.Ф (к.п.н., доцент), Юдина Г.Е. (доцент)
В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение в экономическом планировании и экономических исследованиях. Успешно развиваются методы оптимального планирования, составляющих сущность математического программирования. Задачи целочисленного программирования довольно специфичны, могут часто встречаться на практике. Достаточно указать на то, что партии некоторых видов продукции принципиально целочисленны.
Сформулируем основную задачу линейного программирования, в которой переменные могут принимать только целые значения.
В общем виде задачу можно записать так:
n
F(х) = Еcjxj ® max (1)
j=1
при условиях
n _
Е avxj = bi'i = 1m (2)
j=1
Xj > 0, j = In (3)
xj - целые, j = 1,n (4).
Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (1-4) без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план - оптимальный план задачи целочисленного программирования. Если же в оптимальном плане х] дробная компонента, то к системе
уравнений (2) добавляют неравенство:
Е f (a)Xj > f (b) (5)
j
и находят решение задачи (1-4),(5). Отметим, что в неравенстве (5) а %, ь * - преобразованные исходные величины at] и bt, значения которых
взяты из последней симплексной таблицы, а числа f (a *1}), f (b%) - дробные части чисел. Напомним, что под дробной частью некоторого числа a понимается наименьшее неотрицательное число b такое, что разность
278
|
