Реализация алгоритма Гомори на языке программирования Object Pascal при использовании среды разработки Borland Delphi 7. Рассмотрение основных способов компьютерного осуществления решения задач целочисленного программирования симплексным методом.
Аннотация к работе
Глава 1. Метод Гомори 1.1 Экономическая сущность задачи 1.2 Постановка задачи 1.3 Метод решения задач 1.4 Функциональные тесты Глава 2. Такие задачи называются задачами целочисленного программирования. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Определим максимальное значение целевой функции F(X) = 16x1 9x2 при следующих условиях-ограничений. 5x1 2x2 1x3 0x4 = 20 1x1 1x2 0x3 1x4 = 6 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: Базис B x1 x2 x3 x4 x3 20 5 2 1 0 x4 6 1 1 0 1 F(X0) 0 -16 -9 0 0 Базис B x1 x2 x3 x4 x3 20 5 2 1 0 4 x4 6 1 1 0 1 6 F(X1) 0 -16 -9 0 0 0 Базис B x1 x2 x3 x4 min x1 4 1 2/5 1/5 0 10 x4 2 0 3/5 -1/5 1 31/3 F(X2) 64 0 -23/5 31/5 0 0 Базис B x1 x2 x3 x4 x1 22/3 1 0 1/3 -2/3 x2 31/3 0 1 -1/3 12/3 F(X3) 722/3 0 0 21/3 41/3 Оптимальный план можно записать так: x1 = 22/3 x2 = 31/3 F(X) = 16•22/3 9•31/3 = 722/3 В Оптимальном векторе есть нецелые числа, следует применить метод Гомори Базис B x1 x2 x3 x4 x5 x1 22/3 1 0 1/3 -2/3 0 x2 31/3 0 1 -1/3 12/3 0 x5 -2/3 0 0 -1/3 -1/3 1 F(X0) -722/3 0 0 -21/3 -41/3 0 Базис B x1 x2 x3 x4 x5 x1 22/3 1 0 1/3 -2/3 0 x2 31/3 0 1 -1/3 12/3 0 x5 -2/3 0 0 -1/3 -1/3 1 F(X) -722/3 0 0 -21/3 41/3 0 ? 0 - - -21/3 : (-1/3) = 7 -41/3 : (-1/3) = 13 - Базис B x1 x2 x3 x4 x5 x1 2 1 0 0 -1 1 x2 4 0 1 0 2 -1 x3 2 0 0 1 1 -3 F(X0) -68 0 0 0 -2 -7 Базис B x1 x2 x3 x4 x5 x1 2 1 0 0 -1 1 x2 4 0 1 0 2 -1 x3 2 0 0 1 1 -3 F(X0) -68 0 0 0 -2 -7 Решение получилось целочисленным.