Главная » Программирование

Калькулятор задачи целочисленного линейного программирования

Содержание
  1. Метод Гомори
  2. Виды алгоритма Гомори
  3. Онлайн Калькулятор: Симплекс Метод
  4. Пример решения

Метод Гомори

Метод Гомори используют для нахождения целочисленного решения в задачах линейного программирования.
Пусть найдено решение задачи ЛП: . Решение Li будет целым числом, если т.е. . i> — дробная часть нецелочисленного оптимального решения xi, i> — дробная часть не базисных переменных. Данное соотношение определяет правильное отсечение Гомори (см. рисунок).

Инструкция . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее . Полученное решение сохраняется в файле Word . Дополнительно создается шаблон решения в формате Excel . При этом ограничения типа xi ≥ 0 не учитывайте.

Виды алгоритма Гомори

  1. Первый алгоритм Гомори решения полностью целочисленных задач.
  2. Второй алгоритм Гомори для частично целочисленных задач линейного программирования.
  1. Решается задача линейного программирования без учета целочисленности.
  2. Среди дробных чисел выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение.
  3. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной.
  4. Полученная задача решается двойственным симплекс-методом.

Геометрическая интерпретация отсечения Гомори

Геометрическая интерпретация отсечения Гомори Пример . Научно-производственное объединение «Стрела» занимается изготовлением комплектующих изделий для предприятий ВПК. При изготовлении изделий типа А и типа В используются сталь и цветные металлы. Технологический процесс также включает обработку изделий на токарных и фрезерных станках. По технологическим нормам на производство одного изделия типа А и одного изделия типа В требуется определенное количество сырья и некоторый объем станко-часов для обработки на станках в цеху. Технологические данные производственного процесса приведены в таблице.
В течение месяца цеха НПО «Стрела» располагает ограниченными ресурсами по сырью и по времени работы в производственных цехах (см. таблицу). Прибыль от реализации одного изделия типа А составляет 100 руб., а от единицы изделия типа В – 250 руб.

Читайте также:  Программирование на си для stm32
Сырье Работа в цеху, станко-час Прибыль от реализации, руб.
Цветные металлы Сталь Токарные работы Фрезерные работы
Изделие А 10 25 41 90 100
Изделие В 30 25 90 50 250
Ресурсы 4500 6250 14100 18000

Найти оптимальный план производства для НПО «Стрела» (количество изделия типа А и типа В – целые числа), дающий наибольшую прибыль. Решение.
Экономико-математическая модель задачи.
x1 – план производства изделий типа А, x2 – план производства изделий типа В,
x1, x2 — целые числа.
Ограничения по ресурсам
10x1 + 30x2 ≤ 4500
25x1 + 25x2 ≤ 6250
41x1 + 90x2 ≤ 14100
90x1 + 50x2 ≤ 18000
Целевая функция
100x1 + 250x2 → max Решим прямую задачу линейного программирования симплексным методом. В результате получаем следующий оптимальный план:

Базис B x1 x2 x3 x4 x5 x6
x2 1450 /11 0 1 41 /330 0 -1 /33 0
x4 17500 /11 0 0 245 /66 1 -50 /33 0
x1 600 /11 1 0 -3 /11 0 1 /11 0
x6 6500 0 0 55 /3 0 -20 /3 1
F(X3) 422500 /11 0 0 125 /33 0 50 /33 0

x1 = 54 6 /11, x2 = 131 9 /11
F(X) = 250•131 9 /11 + 100•54 6 /11 = 38409 1 /11 Полученный оптимальный план не является целочисленным, поэтому применяем метод Гомори. Наибольшая дробная часть находится во втором уравнении у переменной x4 ( 10 /11). Составляем дополнительное ограничение:
q2 — q21•x1 — q22•x2 — q23•x3 — q24•x4 — q25•x5 — q26•x6≤0
q2 = b2 — [b2] = 1590 10 /11 — 1590 = 10 /11
q21 = a21 — [a21] = 0 — 0 = 0
q22 = a22 — [a22] = 0 — 0 = 0
q23 = a23 — [a23] = 3 47 /66 — 3 = 47 /66
q24 = a24 — [a24] = 1 — 1 = 0
q25 = a25 — [a25] = -1 17 /33 + 2 = 16 /33
q26 = a26 — [a26] = 0 — 0 = 0
Дополнительное ограничение имеет вид:
10 /11— 47 /66x3— 16 /33x5 ≤ 0
Преобразуем полученное неравенство в уравнение:
10 /11— 47 /66x3— 16 /33x5 + x7 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование F(x) = -F(X).

Читайте также:  Программирование радиостанций универсальный программатор
Базис B x1 x2 x3 x4 x5 x6 x7
x2 1450 /11 0 1 41 /330 0 -1 /33 0 0
x4 17500 /11 0 0 245 /66 1 -50 /33 0 0
x1 600 /11 1 0 -3 /11 0 1 /11 0 0
x6 6500 0 0 55 /3 0 -20 /3 1 0
x7 -10 /11 0 0 -47 /66 0 -16 /33 0 1
F(X0) -422500 /11 0 0 -125 /33 0 -50 /33 0 0

Первая итерация Гомори. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных выбираем наибольшее по модулю. Ведущей будет пятая строка, а переменную x7 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует пятому столбцу, т.е. переменную x5 необходимо ввести в базис. На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный ( -16 /33).

Базис B x1 x2 x3 x4 x5 x6 x7
x2 131 9 /11 0 1 41 /330 0 -1 /33 0 0
x4 1590 10 /11 0 0 3 47 /66 1 -1 17 /33 0 0
x1 54 6 /11 1 0 -3 /11 0 1 /11 0 0
x6 6500 0 0 18 1 /3 0 -6 2 /3 1 0
x7 -10 /11 0 0 -47 /66 0 -16 /33 0 1
F(X0) -38409 1 /11 0 0 -3 26 /33 0 -1 17 /33 0 0
θ — — -3 26 /33 : ( -47 /66) = 5 15 /47 — -1 17 /33 : ( -16 /33) = 3 1 /8 — —

4. Пересчет симплекс-таблицы выполняем с помощью метода Жордано-Гаусса.

Базис B x1 x2 x3 x4 x5 x6 x7
x2 1055 /8 0 1 27 /160 0 0 0 -1 /16
x4 6375 /4 0 0 95 /16 1 0 0 -25 /8
x1 435 /8 1 0 -13 /32 0 0 0 3 /16
x6 13025 /2 0 0 225 /8 0 0 1 -55 /4
x5 15 /8 0 0 47 /32 0 1 0 -33 /16
F(X0) -153625 /4 0 0 -25 /16 0 0 0 -25 /8

В полученном оптимальном плане присутствуют дробные числа. По первому уравнению с переменной x2, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 7 /8, составляем дополнительное ограничение:
q1 — q11•x1 — q12•x2 — q13•x3 — q14•x4 — q15•x5 — q16•x6 — q17•x7≤0
q1 = b1 — [b1] = 131 7 /8 — 131 = 7 /8
q11 = a11 — [a11] = 0 — 0 = 0
q12 = a12 — [a12] = 1 — 1 = 0
q13 = a13 — [a13] = 27 /160 — 0 = 27 /160
q14 = a14 — [a14] = 0 — 0 = 0
q15 = a15 — [a15] = 0 — 0 = 0
q16 = a16 — [a16] = 0 — 0 = 0
q17 = a17 — [a17] = -1 /16 + 1 = 15 /16
Дополнительное ограничение имеет вид:
7 /8— 27 /160x3— 15 /16x7 ≤ 0
Преобразуем полученное неравенство в уравнение:
7 /8— 27 /160x3— 15 /16x7 + x8 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 1055 /8 0 1 27 /160 0 0 0 -1 /16 0
x4 6375 /4 0 0 95 /16 1 0 0 -25 /8 0
x1 435 /8 1 0 -13 /32 0 0 0 3 /16 0
x6 13025 /2 0 0 225 /8 0 0 1 -55 /4 0
x5 15 /8 0 0 47 /32 0 1 0 -33 /16 0
x8 -7 /8 0 0 -27 /160 0 0 0 -15 /16 1
F(X0) -153625 /4 0 0 -25 /16 0 0 0 -25 /8 0

Вторая итерация Гомрои. 1. Проверка критерия оптимальности. План в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной. Среди отрицательных значений базисных переменных наибольшей по модулю является переменная x8. Ее следует вывести из базиса.
3. Минимальное значение θ соответствует седьмому столбцу, т.е. переменную x7 необходимо ввести в базис.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 131 7 /8 0 1 27 /160 0 0 0 -1 /16 0
x4 1593 3 /4 0 0 5 15 /16 1 0 0 -3 1 /8 0
x1 54 3 /8 1 0 -13 /32 0 0 0 3 /16 0
x6 6512 1 /2 0 0 28 1 /8 0 0 1 -13 3 /4 0
x5 1 7 /8 0 0 1 15 /32 0 1 0 -2 1 /16 0
x8 -7 /8 0 0 -27 /160 0 0 0 -15 /16 1
F(X0) -38406 1 /4 0 0 -1 9 /16 0 0 0 -3 1 /8 0
θ — — -1 9 /16 : ( -27 /160) = 9 7 /27 — — — -3 1 /8 : ( -15 /16) = 3 1 /3 —

4. Выполняем преобразование Новых отсечений Гомори.

Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 1979 /15 0 1 9 /50 0 0 0 0 -1 /15
x4 4790 /3 0 0 13 /2 1 0 0 0 -10 /3
x1 271 /5 1 0 -11 /25 0 0 0 0 1 /5
x6 19576 /3 0 0 153 /5 0 0 1 0 -44 /3
x5 19 /5 0 0 46 /25 0 1 0 0 -11 /5
x7 14 /15 0 0 9 /50 0 0 0 1 -16 /15
F(X0) -115210 /3 0 0 -1 0 0 0 0 -10 /3

В оптимальном плане присутствуют дробные числа. Наибольшая дробная часть у переменной x2 ( 14 /15). Составляем дополнительное ограничение: q1 — q11•x1 — q12•x2 — q13•x3 — q14•x4 — q15•x5 — q16•x6 — q17•x7 — q18•x8≤0
q1 = b1 — [b1] = 131 14 /15 — 131 = 14 /15
q11 = a11 — [a11] = 0 — 0 = 0
q12 = a12 — [a12] = 1 — 1 = 0
q13 = a13 — [a13] = 9 /50 — 0 = 9 /50
q14 = a14 — [a14] = 0 — 0 = 0
q15 = a15 — [a15] = 0 — 0 = 0
q16 = a16 — [a16] = 0 — 0 = 0
q17 = a17 — [a17] = 0 — 0 = 0
q18 = a18 — [a18] = -1 /15 + 1 = 14 /15
Дополнительное ограничение имеет вид:
14 /15— 9 /50x3— 14 /15x8 ≤ 0
Преобразуем полученное неравенство в уравнение:
14 /15— 9 /50x3— 14 /15x8 + x9 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x2 1979 /15 0 1 9 /50 0 0 0 0 -1 /15 0
x4 4790 /3 0 0 13 /2 1 0 0 0 -10 /3 0
x1 271 /5 1 0 -11 /25 0 0 0 0 1 /5 0
x6 19576 /3 0 0 153 /5 0 0 1 0 -44 /3 0
x5 19 /5 0 0 46 /25 0 1 0 0 -11 /5 0
x7 14 /15 0 0 9 /50 0 0 0 1 -16 /15 0
x9 -14 /15 0 0 -9 /50 0 0 0 0 -14 /15 1
F(X0) -115210 /3 0 0 -1 0 0 0 0 -10 /3 0

Третья итерация методом Гомори. Переменную x9 следует вывести из базиса. Минимальное значение θ соответствует восьмому столбцу, т.е. переменную x8 необходимо ввести в базис.

Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x2 131 14 /15 0 1 9 /50 0 0 0 0 -1 /15 0
x4 1596 2 /3 0 0 6 1 /2 1 0 0 0 -3 1 /3 0
x1 54 1 /5 1 0 -11 /25 0 0 0 0 1 /5 0
x6 6525 1 /3 0 0 30 3 /5 0 0 1 0 -14 2 /3 0
x5 3 4 /5 0 0 1 21 /25 0 1 0 0 -2 1 /5 0
x7 14 /15 0 0 9 /50 0 0 0 1 -1 1 /15 0
x9 -14 /15 0 0 -9 /50 0 0 0 0 -14 /15 1
F(X0) -38403 1 /3 0 0 -1 0 0 0 0 -3 1 /3 0
θ — — -1 : ( -9 /50) = 5 5 /9 — — — — -3 1 /3 : ( -14 /15) = 3 4 /7 —

4. Выполняем преобразование.

Базис B x1 x2 x3 x4 x5 x6 x7 x8 x9
x2 132 0 1 27 /140 0 0 0 0 0 -1 /14
x4 1600 0 0 50 /7 1 0 0 0 0 -25 /7
x1 54 1 0 -67 /140 0 0 0 0 0 3 /14
x6 6540 0 0 234 /7 0 0 1 0 0 -110 /7
x5 6 0 0 317 /140 0 1 0 0 0 -33 /14
x7 2 0 0 27 /70 0 0 0 1 0 -8 /7
x8 1 0 0 27 /140 0 0 0 0 1 -15 /14
F(X0) -38400 0 0 -5 /14 0 0 0 0 0 -25 /7

Решение получилось целочисленным. Оптимальный целочисленный план можно записать так: x1 = 54, x2 = 132. F(X) = 38400

Источник

Онлайн Калькулятор: Симплекс Метод

  • English
  • Русский

  • Simplex Method

    Google Play Icon1App Store Icon

    Пример решения

    000 2x1 + x2 ≤ 600
    0x1 + 0x2 ≤ 225
    5x1 +4x2 ≤ 1000
    2x2 ≥ 150
    0x1 + 0x2 ≥ 0

    arrow transition

    000 2x1 + x2 + x3 = 600
    + x4 = 225
    5x1 + 4x2 + x5 = 1000
    2x2 — x6 + x8 = 150
    — x7 + x9 = 0

    Предварительный этап:

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

    Далее необходимо избавиться от неравенств, для чего в левую часть неравенств вводим компенсирующие переменные. Если неравенство вида ≤, то компенсирующая переменная имеет знак +, если неравенство вида ≥, то компенсирующая переменная имеет знак -. Компенсирующие переменные входят в целевую функцию задачи с нулевым коэффициентом.

    Теперь в системе ограничений необходимо найти достаточное количество базисных переменных. В каждом ограничении должна быть одна базисная переменная. Базисной является переменная, которая имеет при себе коэффициент 1 и встречается только в одном ограничении. Если в каком-то ограничении нет базисных переменных, то добавляем их искусственно, причем искусственные переменные входят в целевую функцию с коэффициентом -M, если целевая функция стремится к мах и с М, если целевая функция стремится к min.

    B Cb P x1 x2↓ x3 x4 x5 x6 x7 x8 x9 Q
    3 4 0 0 0 0 0 -M -M
    x3 0 600 2 1 1 0 0 0 0 0 0 600
    x4 0 225 0 0 0 1 0 0 0 0 0 ∞
    x5 0 1000 5 4 0 0 1 0 0 0 0 250
    x8
    ←    		 -M 150 0 2 0 0 0 -1 0 1 0 75
    x9 -M 0 0 0 0 0 0 0 -1 0 1 ∞
    max -150M -3 -2M-4 0 0 0 M M 0 0

    Вычисление элементов таблицы:

    Переносим в таблицу базовые элементы, которые мы определили на предварительном этапе:

    Каждая ячейка этого столбца равна коэффициенту, который соответствует базовой переменной в соответствующей строке.

    Значения упрявляемых переменных и колонки P

    На данном этапе никаких вычислений не нужно, просто переносим значения из предварительного этапа в соответствующие ячейки таблицы:

    Источник

    • Оцените статью
    © 2024 Программирование