Решение прямой и двойственной задачи линейного программирования средствами Python

    Введение


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

    Постановка задачи


    В публикациях [1,2] рассматривались решения прямых задач оптимизации методом линейного программирования и был предложен обоснованный выбор решателя scipy. optimize.

    Однако известно [3], что каждой задаче линейного программирования соответствует так называемая выделенная(двойственная)задача. В ней по сравнению с прямой задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума — максимум). Задача, двойственная к двойственной — эта сама исходная задача.

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

    Оптимальные значения стоимости материала и труда будут оцениваться по их вкладу в целевую функцию. В результате будут получены «объективно обусловленные оценки» сырья и рабочей силы, которые не совпадают с рыночными ценами.

    Решение прямой задачи о оптимальной производственной программе


    Учитывая высокий уровень математической подготовки подавляющего большинства пользователей данного ресурса не стану приводить балансовые уравнения с верхними и нижними ограничениями и введением для перехода к равенствам дополнительных переменных. Поэтому сразу приведу обозначения используемых в решении переменных:
    N – количество видов производимых изделий;
    m– количество видов используемого сырья;
    b_ub — вектор имеющихся ресурсов размерности m;
    A_ub – матрица размерности m×N, каждый элемент которой является расходом ресурса вида i на производство единицы изделия вида j;
    с — вектор прибыли от производства единицы изделия каждого вида;
    x – искомые объёмы производимых изделий каждого вида (оптимальный план производства) обеспечивающие максимальную прибыль.

    Функция цели
    maxF(x)=c×x

    Ограничения
    A×x≤b

    Численные значения переменных:
    N=5; m=4; b_ub = [700,250,600,400]; A_ub = [[1,2,3,2,4], [5,4,3,2,1], [3,4,2,5,3],[4,2,5,3,1]]; c = [25, 35,25,40,30].

    Задачи
    1.Найти x для обеспечения максимальной прибыли
    2. Найти использованные ресурсы при выполнении п.1
    3. Найти остатки ресурсов (если они есть) при выполнении п.1

    Особенности решения с библиотекой scipy. optimize
    Для определения максимума (по умолчанию определяется минимум коэффициенты целевой функции нужно записать с отрицательным знаком c = [-25, -35,-25,-40,-30] и проигнорировать знак минус перед прибылью.

    Используемые при выводе результатов обозначения:
    x – массив значений переменных, доставляющих минимум (максимум) целевой функции;
    slack – значения дополнительных переменных. Каждая переменная соответствует ограничению-неравенству. Нулевое значение переменной означает, что соответствующее ограничение активно;
    success – True, если функции удалось найти оптимальное решение;
    status – статус решения:
    0 – поиск оптимального решения завершился успешно;
    1 – достигнут лимит на число итераций;
    2 – задача не имеет решений;
    3 – целевая функция не ограничена.
    nit – количество произведенных итераций.

    Листинг решения прямой задачи оптимизации
    #!/usr/bin/python
    # -*- coding: utf-8 -*-
    import scipy
    from scipy.optimize import linprog # загрузка библиотеки ЛП
    c = [-25, -35,-25,-40,-30] # список коэффициентов функции цели
    b_ub = [700,250,600,400] # список объёмов ресурсов
    A_ub = [[1,2,3,2,4], # матрица удельных значений ресурсов
                   [5,4,3,2,1],
                  [3,4,2,5,3],
                  [4,2,5,3,1]] 
    d=linprog(c, A_ub, b_ub) # поиск решения
    for key,val in d.items():
             print(key,val) # вывод решения
             if key=='x':
                      q=[sum(i) for i in A_ub*val]#использованные ресурсы
                      print('A_ub*x',q) 
                      q1= scipy.array(b_ub)-scipy.array(q) #остатки ресурсов
                      print('b_ub-A_ub*x', q1)
    

    Результаты решения задачи
    nit 3
    status 0
    message Optimization terminated successfully.
    success True
    x [ 0. 0. 18.18181818 22.72727273 150. ]
    A_ub*x [700.0, 250.0, 600.0, 309.09090909090912]
    b_ub-A_ub*x [ 0. 0. 0. 90.90909091]
    fun -5863.63636364
    slack [ 0. 0. 0. 90.90909091]

    Выводы

    1. Найден оптимальный план по видам продукции [0.0 0. 0 18.182 22.727 150. 0]
    2. Найдено фактическое использование ресурсов [700.0, 250.0, 600.0, 309.091]
    3. Найден остаток не использованного четвёртого вида ресурса [ 0. 0 0.0 0.0 90.909]
    4. Нет необходимости в вычислениях по п.3, так как тот же результат выводить в переменной slack

    Решение двойственной задачи о оптимальной производственной программе


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

    Введём новое назначение искомой переменной x как некоторой «теневой» цены, определяющей ценность данного ресурса в отношении прибыли от реализации выпускаемой продукции.

    Далее для сравнительного анализа частично сохраним ранее принятые обозначения, но с новым содержанием:

    c – вектор имеющихся ресурсов;
    b_ub – вектор прибыли от производства единицы изделия каждого вида;
    A_ub_T– транспонированная матрица A_ub.

    Функция цели
    minF(x)=c×x

    Ограничения
    A_ub_T ×x≥ b_ub

    Численные значения и соотношения для переменных:
    с = [700,250,600,400]; A_ub_T transpose(A_ub); b_ub = [25, 35,25,40,30].

    Задача:
    Найти x показывающий ценность для производителя каждого вида ресурсов.

    Особенности решения с библиотекой scipy. optimize
    Для замены ограничений сверху на ограничения с низу необходимо умножить на минус единицу обе части ограничения – A_ub_T ×x≥ b_ub… Для этого исходные данные записать в виде: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

    Листинг решения двойственной задачи оптимизации
    #!/usr/bin/python
    # -*- coding: utf-8 -*-
    import scipy
    from scipy.optimize import linprog
    A_ub = [[1,2,3,2,4], 
                   [5,4,3,2,1],
                  [3,4,2,5,3],
                  [4,2,5,3,1]] 
    c=[700,250,600,400] 
    b_ub = [-25, -35,-25,-40,-30]
    A_ub_T =-scipy.transpose(A_ub)
    d=linprog(c, A_ub_T, b_ub)
    for key,val in d.items():
             print(key,val)
    

    Результаты решения задачи
    nit 7
    message Optimization terminated successfully.
    fun 5863.63636364
    x [ 2.27272727 1.81818182 6.36363636 0. ]
    slack [ 5.45454545 2.27272727 0. 0. 0. ]
    status 0
    success True

    Выводы


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

    Результаты сравнения прямой и двойственной задачи


    1. Двойственная задача расширяет возможности планирования выпуска продукции, но средствами scipy. optimize решается за вдвое большее чем прямая количество итераций.
    2. Переменная slack выводит информацию об активности ограничений в виде неравенств, что может быть использовано, например, для анализа остатков сырья.
    3. Прямая задача является задачей максимизации, а двойственная — задачей минимизации, и наоборот.
    4. Коэффициенты функции цели в прямой задаче являются ограничениями в двойственной задаче.
    5. Ограничения в прямой задаче становятся коэффициентами функции цели в двойственной.
    6. Знаки неравенств в ограничениях меняются на противоположные.
    7. Матрица системы равенств транспонируется.

    Ссылки

    1. Решение закрытой транспортной задачи с дополнительными условиями средствами Python.
    2. Решение задач линейного программирования с использованием Python.
    3. Двойственность в задачах линейного программирования.
    Метки:
    • +14
    • 4,4k
    • 3
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 3
    • 0
      О эти названия переменных! Обожаю код, написанный математиками или физиками.
      • +1
        Ну задачи то могут быть довольно абстрактными, к ЛП можно много чего свести. В наиболее общем случае Ax = b есть просто запись абстрактной СЛУ, задающей ограничения. И имена а-ля systemMatrix или rightHandSideOfEquationsSystem будут выглядеть также глупо, как имена firstCounter, secondCounter вместо счётчиков i, j
        • +1
          Даже в случае полностью абстрактного кода лучше написать «systemMatrix или rightHandSideOfEquationsSystem» (только не в CamelCase, конечно), чем потом или самому гадать что это за A и b, забыв для чего был код, или ставить в неловкой положение программиста, решившего поковыряться в сорсах.
          По моему опыту учёные даже в гораздо более конкретных примерах предпочитают переносить уравнения в код как есть.

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