Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.
Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.
Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.
Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.
Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.
Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.
Аннотация лекции. Лекция посвящена симплекс-методу решения задачи линейного программирования (методу искусственного базиса). Рассмотрен алгоритм двухэтапного симплекс-метода.
Как было рассмотрено в разделе 3, для применения алгоритма симплекс-метода необходимо начать решение задачи линейного программирования с некоторого опорного плана. Чтобы этот план можно было построить, задача должна быть записана в канонической форме с неотрицательными свободными членами и иметь полный набор базисных переменных.
Любая задача линейного программирования может быть приведена к канонической форме. Если при этом среди ее свободных членов имеются отрицательные, то, умножив обе части соответствующего ограничения на -1, легко добиться неотрицательности всех свободных членов. Однако не всякая задача содержит готовый базис. Если его нет, используются методы искусственного базиса. Применение таких методов обеспечивает универсальность симплекс-метода, т.е. возможность решать с его помощью любую задачу линейного программирования.
Рассмотрим одну из модификаций метода искусственного базиса – двухэтапный симплекс-метод.
4.1 Двухэтапный симплекс-метод
Пусть задача линейного программирования в канонической форме с неотрицательными свободными членами не содержит полного набора базисных переменных:
max n
∑cj xj
min j 1=
(18)
∑n aij xj = bi , i =1,m
j 1=
xj ≥ 0, j =1,n
В этом случае, для того чтобы применить к ней симплекс-метод, используется метод искусственного базиса. Вводят m неотрицательных переменных у1, у2, . . . . уm, по одной в каждое уравнение. Эти переменные называют искусственными, и составляют расширенную задачу, имеющую следующий вид (Обратите внимание, что целевая функция задачи (19) всегда минимизируется, независимо от того, на минимум или на максимум поставлена задача (18)):
m min∑yi
i 1=
∑n aijx j + yi = bi, i =1,m (19)
j 1=
x j ≥ 0, j =1,n
yi ≥ 0, i =1,m
В этой задаче имеется m единичных столбцов при искусственных переменных, из которых и состоит искусственный базис.
Лемма. Задача (19) всегда разрешима.
Доказательство. Очевидно, что область допустимых планов (ОДП) этой задачи не может быть пуста: налицо хотя бы один допустимый план - тот опорный план, который соответствует исходному базису. В самом деле, план Х = (х1, x2, …, xn, y1, y2, …, ym) = (0, 0, …, 0, b1, b2, …, bm) ∈ ОДП задачи (19).
Целевая функция не может быть не ограничена, так как не может быть меньше нуля (она представляет собой сумму неотрицательных переменных). Лемма доказана.
Пусть U* = (x1*, . . . xn*, y1*, . . . ym*) - оптимальный план задачи (19). Теорема о свойствах оптимального плана расширенной задачи:
m
*
1). > 0 ⇒ОДП(исходной задачи) =∅
i
Т.е. если оптимум расширенной задачи положителен (что эквивалентно утверждению о том, что хотя бы одна искусственная переменная в плане U* положительна), то ОДП исходной задачи пуста.
m
* (0) * *
2). = 0 ⇒X = (x1 ,...,xn)∈ОДП(исходной задачи)
i
Другими словами, если в U* все искусственные переменные равны 0, то план Х(0), составленный из компонент xj* плана U*, является допустимым для исходной задачи.
Доказательство первой части теоремы осуществляется от противного. Предположим, что существует уi* > 0, и ОДП задачи (18) при этом не пуста, т.е. существует план X` = (x1`,. . . . xn`) ∈ ОДП задачи (18). Рассмотрим план U` = (x1`,. . . xn`, 0 ... 0 ) (в нем
14243
m первые n компонент взяты из плана X`, а все искусственные переменные равны нулю). U`∈ ОДП задачи (19), что легко проверить подстановкой его в систему ограничений этой задачи:
∑j 1=n aijx j`+ 0 = bi, i =1,m ∑n aijx j`= bi, i =1,m
0x ≥`≥00, j =1,n ⇔j 1= x j`≥ 0, j =1,n j
Последняя система истинна, так как X`∈ ОДП задачи (18).
На плане U` целевая функция задачи (19) Z` = 0 (сумма нулевых искусственных переменных). Однако по условию теоремы, оптимум задачи (19) положителен, т.е. больше Z`. Так как задача (19) на минимум, план U* не может быть оптимальным, если есть допустимый план, на котором значение целевой функции меньше. Мы пришли к противоречию, первая часть теоремы доказана.
Вторая часть теоремы доказывается непосредственно подстановкой
Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.
Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.
Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.
Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.
Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.
Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.