Выпуклое программирование онлайн

Пример решения задачи — выпуклое программирование.

Ниже приведено условие и решение задачи. Закачка решения в формате doc начнется автоматически через 10 секунд.

Предприятие выпускает изделия А и Б, при изготовлении которых используется сырье С 1 и С 2 . Известны запасы b i ( i = 1,2) сырья, нормы a ij ( j = 1,2) его расхода на единицу изделия, оптовые цены р j на изделия и их плановая себестоимость с j 0 . Как только объем выпускаемой продукции перестанет соответствовать оптимальным размерам предприятия, дальнейшее увеличение выпуска х j ведет к повышению себестоимости продукции и в первом приближении фактическая себестоимость с j описывается функцией с j = с j 0 + с j ′ х j , где с j ′ — некоторая постоянная величина. При поиске плана выпуска изделий, обеспечивающего предприятию наивысшую прибыль в условиях нарушения баланса между объемом выпуска и оптимальными размерами предприятия, целевая функция принимает вид f = ( p 1 – ( c 1 0 + c 1 ′ x 1 )) x 1 + + . ( p 2 – ( c 2 0 + c 2 ′ x 2 )) x 2 , а ограничения по сырью а 11 х 1 + а 12 х 2 ≤ b 1 , а 21 х 1 + а 22 х 2 ≤ b 2 , х 1 ≥ 0, х 2 ≥ 0.

составить экономико-математическую модель задачи применительно к числовым данным выполняемого варианта;

графическим методом решить полученную задачу и сформулировать ответ в экономических терминах в соответствии с условиями задачи.

Целевая функция данной задачи имеет следующий вид:

f ( X 1 , X 2 ) = ( 8- ( 6 + 0,1 X 1 )) X 1 + ( 7- ( 4 + 0,1 X 2 )) X 2

Упростив ее, получим искомую математическую модель с учетом ограничений на запасы сырья:

f = 2 X 1 — 0,1 X 1 2 + 3 X 2 – 0,1 X 2 2 max

5Х 1 + 2Х 2 ≤ 30

8Х 1 + 11Х 2 ≤ 60

Целевая функция определяет в трехмерном пространстве параболоид вращения. В пересечении этого па раболоида с плоскостями, параллельными координатной плоскости X 1 OX 2 , будут окружности с центрами на оси параболоида. Каждой такой окружности отвечает определенное значение функции f . Поэтому линиями уровня функции f будут концентрические окружности с общим центром в точке Р, являющейся проекцией оси параболоида на плоскость X 1 OX 2 . Чтобы найти координаты точки Р и радиусы этих окружностей, преоб ­ разуем целевую функцию f , выделив в ней полные квадраты относительно переменных Х 1 и Х 2 :

-10 ∙f = X 1 2 – 20X 1 + X 2 2 – 30X 2

-10 ∙f = X 1 2 – 20X 1 + 100 + X 2 2 – 30X 2 + 225 — 325

325 — 10∙ f = ( X 1 – 10) 2 + ( X 2 – 15) 2

Итак, к оординаты точки Р равны (1 0, 15 ), а радиусы г окружностей вычисляются по формуле: r = 325 — 10∙ f

Множество планов X данной задачи определяет на координатной плоскости X 1 OX 2 многоуголь ник ОАВС, изображенный на рис. 5.1. На этом же рисунке изображены линии уровня.

Как видно из рис. 5.1, координаты точки М* из области О ABC , через которую проходит линия уровня, отвечающая максимальному значению функции f , находятся из системы уравнений

8Х 1 + 11Х 2 = 60

(Х 2 — 15 ) = 11/8 (Х 1 — 10 )

где уравнение 8 Х 1 + 11 Х 2 = 60 задает граничную прямую , а уравнение (Х 2 — 15 ) = 11/8 (Х 1 — 10 ) задает прямую

РМ проходящую через точку М перпендикулярно прямой (угловой коэффициент этой прямой равен — 1/ k , где k — угловой коэф фициент граничной прямой, равный 11/8 ). Решим данную систему:

8Х 1 + 11Х 2 = 60 X 1 = 2

(Х 2 — 15 ) = 11/8 (Х 1 — 10 ) X 2 = 4

из решения М=(2,4 ), значение целевой функции f (М)= 2∙2 – 0,1∙2 2 + 4∙3 – 0,1∙4 2 = 14 в этой точке. Итак, для получения предприятием максимальной прибыли, составляющей 14 д ен. ед., следует выпустить 2 ед. изделий первого вида и 4 ед. изделия второго вида.

Имя файла: mathprog3.doc

Размер файла: 58.5 Kb

Если закачивание файла не начнется через 10 сек, кликните по этой ссылке

Калькулятор симплекс-метода

Выполнено действий: 148

Как пользоваться калькулятором

• Задайте количество переменных и ограничений
• Введите коэффициенты целевой функции
• Введите коэффициенты ограничений и выберите условия (≤, = или ≥)
• Выберите тип решения
• Нажмите кнопку «Решить»

Что умеет калькулятор симплекс-метода

• Решает основную задачу линейного программирования
• Позволяет получить решение с помощью основного симплекс-метода и метода искусственного базиса
• Работает с произвольным количеством переменных и ограничений

Что такое симплекс-метод

Задача линейного программирования — это задача поиска неотрицательных значений параметров, на которых заданная линейная функция достигает своего максимума или минимума при заданных линейных ограничениях.

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Алгоритм является универсальным методом, которым можно решить любую задачу линейного программирования.

Если вам тоже ничего не понятно из этого определения, то вы на верном пути. Чаще всего статьи про симплекс-метод очень сильно углубляются в дебри теории задачи линейного программирования, из-за чего очень легко потерять суть и так ничего и не понять. Мы постараемся описать алгоритм симплекс-метода так, чтобы показать, что в нём нет ничего страшного и на самом деле он весьма простой. Но сначала нам всё-таки потребуется ввести несколько определений.

Целевая функция — функция, максимум (или минимум) которой нужно найти. Представляет собой сумму произведений коэффициентов на значения переменных: F = c₁·x₁ + c₂·x₂ + . + c_n·x_n

Ограничение — условие вида a₁·x₁ + a₂·x₂ + . + a_n·x_n v b , где вместо v ставится один из знаков: ≤, = или ≥

План — произвольный набор значений переменных x₁ . x_n.

Алгоритм решения основной задачи ЛП симплекс-методом

Пусть в задаче есть m ограничений, а целевая функция заивисит от n основных переменных. Первым делом необходимо привести все ограничения к каноническому виду — виду, в котором все условия задаются равенствами. Для этого предварительно все неравенства с ≥ умножаются на -1, для получения неравенств с ≤.

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

Формирование начального базиса

После того как задача приведена к каноническому виду, необходимо найти начальный базис для формирования первого опорного решения. Если в процессе приведения были добавлены дополнительные переменные, то они становятся базисными.

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

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

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₆
Столбец 4 является частью единичной матрицы. Переменная x₄ входит в начальный базис
В пятом столбце все значения кроме третьего равны нулю. Поэтому в качестве третьей базисной переменной берём x₅ , предварительно разделив третью строку на 2.
Симплекс-таблица

28 cайтов, на которых можно порешать задачи по программированию

• Подборки, 27 октября 2015 в 20:00
• Александр Курилкин

Не секрет, что лучший способ повысить свои навыки в программировании — это практиковаться и только практиковаться. Мы подготовили для вас огромную подборку сайтов с задачами по программированию на самые разные темы.

Codeforces — несомненно самая популярная и известная платформа во всем мире для проведения соревнований на алгоритмику. Кроме крупных контестов сайт зачастую проводит свои «раунды» — участникам даются 5 задач на два часа. Есть система рейтинга, на основе которой участники делятся на два дивизиона. Таким образом, профи не соревнуются с новичками напрямую. Все задачи можно сдать и проверить даже после соревнований. Кроме «раундов» доступны и «тренировки» — задачи с прошедших соревнований публикуются в режиме дорешивания.

TopCoder — ненамного отстающая по популярности от Codeforces американская платформа. Примечательна тем, что кроме алгоритмических контестов, которые описывались ранее, на ней проводятся и соревнования по промышленному программированию и марафоны — соревнования с задачами на исследование, для которых нет единого верного алгоритма, а есть лишь ответ, подходящий больше или меньше. На решение таких задач участникам обычно дается одна или две недели.

Timus Online Judge — русскоязычная (хотя английский язык также поддерживается) платформа, на которой более тысячи задач удачно отсортированы по темам и по сложности. Также тут регулярно проводятся контесты уральского региона, которые, впрочем, не представляют для вас ничего интересного, если только вы не студент УрФУ или другого близлежащего вуза

SPOJ — крупный англоязычный сайт с более чем 20000 задачами на абсолютно разные темы: динамическое программирование, графы, структуры данных и т.д. Изредка проводит контесты, которые не представляют интереса, если вы не живете в странах их проведения.

informatics.mccme.ru — платформа с множеством теоретических материалов и задач по соответствующим темам. Все очень удобно собрано по категориям и темам. Также содержит большую базу задач с прошедших олимпиад школьников.

CodeChef — менее крупный аналог Codeforces и TopCoder, тоже с огромным архивом задач и регулярными контестами.

acmp.ru — сайт, который будет полезен всем благодаря своему архиву задач, удобно (и по большей части правильно) отсортированному по сложности и темам. Соревнования проводятся, но участвовать в них имеет смысл только школьникам Красноярского края, для которых эта платформа изначально и предназначалась.

Project Euler — сборник 500 задач, которые невозможно решить без знаний математических и геометрических алгоритмов. Иногда используется на собеседованиях для приема на работу, чтобы лучше выяснить алгоритмическую подготовку претендента.

Kaggle — данная платформа отличается от описанных ранее тем, что тут не проводится алгоритмических соревнований — только задачи на исследование (как в марафонах на вышеприведенном TopCoder). Например, одна из задач, на которой сейчас там проверяют свои умения участники, состоит в распознании написанных вручную цифр. Вот несколько символов, для которых это не так просто, как кажется (прим. авт. — некоторые из них я не смог распознать даже не программно):

CodinGame — сайт, на котором программирование и видеоигры сливаются в единое целое. Здесь вы найдете большую коллекцию задач на программирование, оформленных в виде видеоигр. Также тут изредка (раз в два месяца) проводятся контесты, содержащие в себе задачи на оптимизацию и ИИ, победители которых получают ценные призы. А если вы решите много задач, то на вас могут обратить внимание компании, которые набирают на этом сайте работников!

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

HackerRank наоборот будет больше интересен профессионалам, которые уже многое умеют. На этом сайте собрано множество задач на самые разные разделы Computer Science: традиционная алгоритмика, ИИ, машинное обучение и т.д. Если вы решите много задач, то вами могут заинтересоваться работодатели, регуляторно мониторящие эту платформу.

C Puzzles — подборка головоломок, специфичный для языка С, со всеми его причудами. Например, дан код, который, по логике, не должен работать, но, тем не менее, он компилируется и даже правильно выполняет свою задачу. Надо понять, почему так? На этой сайте вы сможете приобрести навык отладки программ и чтения кода других.

Codewars — cборник задач на разные темы, от алгоритмов до шаблонов проектирования.

LeetCode — сайт с задачами для подготовки к собеседованиям.

Programming Praxis — блог, включающий в себя много интересных задач.

PythonChallange — сайт с загадками, возрастающими по сложности. Для их решения необходимо написать программу на Python.

Al Zimmermann’s Programming Contests — платформа, на которой раз в полгода проводятся контесты с задачами на исследование и оптимизацию. Интересен тем, что писать программу необязательно — даются только тестовые данные. Ответы можно расчитывать вручную, или просто гадать их на кофейной гуще.

Ruby Quiz — подборка задач для программистов на Ruby, но решения можно писать и на других языках.

Prolog Problems — аналогично с Ruby Quiz. Подборка задач для программистов, использующих Prolog.

MindCipher — сборник занимательных математических и логических задач (в том числе и по программированию).

Сборник задач для практики от СppStudio. Рекомендуется решать на С++, но можно и на других языках.

CheckIO — сайт с задачами для программистов всех уровней, оформленный в виде игры.

E-olimp — украинская тестирующая система с большим архивом задач.

Empire of Code — сайт для программистов, где необходимо писать код, реализующий стратегию и тактику виртуальных бойцов.

Operation Go — практика написания кода на Go в игровой форме.

Russian AI Cup — ежегодный контест от mail.ru по разработке ИИ. Участвовать могут все — от школьников до профессионалов. Победителям и призерам так же полагаются крутые призы. Обязательно примите участие, если вы заинтересованы этой темой.

Задачи Типичного Программиста — да, на нашем сайте тоже есть задачи с собеседований, причем на самые разные темы: от логических и математических до алгоритмических. В эту подборку включены лучшие из них (она регулярно обновляется).

25 бесплатных онлайн-курсов программирования для обучения с нуля

Осваивайте популярные языки не выходя из дома и в удобном для вас темпе.

Java Programming For Complete Beginners

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

Learn to Program in Java

Начальный курс для всех, хочет изучить язык программирования Java и стать разработчиком. Процесс построен таким образом, что слушатели научатся не только писать код, но и решать проблемы, с которыми неизбежно придётся столкнуться при создании приложений.

Java. Быстрый старт

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

Java. Базовый курс

Курс для тех, кто только начинает изучать Java. Лекции содержат материал, охватывающий синтаксис языка, компиляцию программ, основы объектно‑ориентированного программирования и более сложные аспекты Java, а также контрольные вопросы и практические задания.

Android. Быстрый старт

Практический онлайн‑курс для ознакомления с разработкой под Android, требующий базовых знаний Java. В ходе обучения слушатели создадут простую игру, сразу же применяя полученные теоретические знания в деле.

JavaScript

JavaScript для начинающих

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

Основы JavaScript

Очень подробный онлайн‑курс, который поможет изучить JavaScript, начиная с самых азов. Слушатели рассмотрят все аспекты популярного языка программирования от простого к сложному и научатся использовать его на реальных примерах.

Python

Основы языка Python

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

Программирование на Python

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

Python: основы и применение

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

Интерактивные уроки по Python

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

Machine Learning with Python: A Practical Introduction

Вводный онлайн‑курс по основам машинного обучения на Python, который познакомит с различными видами моделирования. Слушатели освоят классификацию, кластеризацию и другие популярные алгоритмы, а также подкрепят полученные теоретические знания практическими навыками.

Введение в программирование (C++)

Базовый курс, который познакомит с основами C++ и поможет прибрести опыт, необходимый для более углублённого изучения программирования. Процесс обучения построен на выполнении множества небольших практических задач, охватывающих все основные конструкции языка.

Introduction to C++

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

Основы C++

Рассчитанный на новичков онлайн‑курс, который посвящён основам языка C++. Охватывает базовые элементы и азы объектно‑ориентированного программирования с примерами и заданиями. Заключительная часть отводится практическому применению полученных навыков.

Программирование на языке C++

Подробный базовый курс по C++, в котором особое внимание уделено основным принципам работы программ и процессу компиляции. Синтаксические конструкции рассматриваются лишь на первой лекции, поэтому слушатели должны быть знакомы с понятиями «переменная», «функция», «цикл».

Углублённое программирование на C/C++

Ориентированный на начинающих разработчиков онлайн‑курс, который предполагает знание основ C++. Материалы помогут приобрести навыки создания программ средней сложности и типовых шаблонов объектно‑ориентированного программирования. Также рассматриваются ключевые аспекты работы с памятью, асинхронные вычисления и диалекты.

C++ Programming — Advanced Features

Более сложный онлайн‑курс, в котором студенты научатся создавать быстрые программы, используя продвинутые возможности C++. Всего за несколько часов лекторы объяснят ключевые расширенные функции этого языка, которые будут закреплены практическими занятиями.

Objective‑C

Become an iOS Developer from Scratch

Обширный и детальный курс, который является пошаговым руководством для всех, кто хочет с нуля освоить Objective‑C и научиться создавать программы для iPhone. В ходе обучения слушатели ознакомятся с пакетом iOS SDK и, применяя доступные инструменты, напишут своё первое полнофункциональное приложение.

Swift

Swift 5: Основы

Очень подробный онлайн‑курс, который подойдёт для новичков без каких‑либо предварительных знаний. В материалы включены основы теории программирования, переменные и константы, циклы и условные конструкции, а также объектно- и протокол‑ориентированное программирование.

Intro to iOS App Development with Swift

Практический онлайн‑курс для тех, кто уже владеет основами, который познакомит с разработкой под iOS на Swift. Слушатели изучат все нюансы этого языка программирования и создадут забавное приложение, искажающее голос (звучит как у бурундука или Дарта Вейдера).

Веб‑разработка

Веб‑разработка. Быстрый старт

Комбинированный курс для тех, кто хочет научиться создавать функциональные сайты с нуля. Слушатели познакомятся с основами HTML и CSS, получат начальные навыки веб‑разработки на PHP, а также освоят логику работы с этим языком, его терминологию и принципы функционирования.

Основы SQL для начинающих

Вводный онлайн‑курс, который откроет основы SQL. На лекциях слушатели узнают, что такое системы управления базами данных, и научатся использовать SQLite, MySQL и другие необходимые для работы инструменты.

PHP базовый курс

Подробный онлайн‑курс для всех желающих освоить веб‑программирование с нуля. На занятиях рассматриваются базовые принципы языка и проблемы, с которыми придётся столкнуться. После завершения программы студенты смогут самостоятельно делать несложные сайты.

Beginner PHP and MySQL Tutorial

Объёмный курс для начинающих программистов, охватывающий все аспекты PHP и MySQL. Обучение построено таким образом, что по окончании занятий можно смело браться за разработку функциональных веб‑приложений.

Электронная библиотека

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

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

Иногда выпуклую функцию называют выпуклой вниз в отличие от вогнутой функции, которую иногда называют выпуклой вверх. Смысл этих названий ясен из геометрического изображения типичной выпуклой (рис. 3.3) и вогнутой (рис. 3.4) функции.

Рис. 3.3. Выпуклая функция

Рис. 3.4. Вогнутая функция

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

Задачей выпуклого программирования называется частный случай общей задачи математического программирования (3.7), (3.8), когда целевая функция и функции ограничений являются вогнутыми на выпуклом множестве R.

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

задачей выпуклого программирования называется также задача минимизации выпуклой функции при ограничениях:

где – выпуклые функции; R – выпуклое множество. Это просто другая форма задачи.

Следует обратить внимание, что если задача выпуклого программирования формулируется как задача на максимум, то целевая функция обязательно вогнута, а если формулируется как задача на минимум – то выпукла, Если ограничения записываются в виде , то функции ограничений вогнуты, если ограничения записываются в виде , то функции ограничений выпуклы. Эта связь обусловлена наличием определенных свойств у задачи выпуклого программирования, которые при нарушении такой связи могут отсутствовать. Два основных таких свойства сформулированы в следующей лемме.

Множество допустимых планов задачи выпуклого программирования

является выпуклым. Любой локальный максимум вогнутой функции на Х является глобальным.

Если бы функции ограничений были выпуклы, то для определяемого множества Х (3.14) выпуклость уже бы не следовала. В этом случае можно доказать выпуклость множества:

Если бы целевая функция была выпукла, то утверждение леммы относительно ее максимумов стало бы неверным, однако аналогичное утверждение можно было бы доказать для минимумов.

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

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

Сумма выпуклых (вогнутых) функций выпукла (вогнута). Произведение выпуклой (вогнутой) функции на положительное число выпукло (вогнуто). Сумма выпуклой (вогнутой) и строго выпуклой (строго вогнутой) функций строго выпукла (строго вогнута).

Если функция строго вогнута (строго выпукла) на выпуклом множестве Х, то у нее может быть только одна точка максимума (минимума).

Предположим противное, т.е. что существует две точки , , являющиеся точками максимума строго вогнутой функции на Х. Обозначив , имеем . Тогда для любого справедливо:

т.е. пришли к противоречию. Аналогично доказывается для минимума строго выпуклой функции.

Линейная функция представляет собой единственный пример одновременно выпуклой и вогнутой функции, значит, она не является строго выпуклой (строго вогнутой). Квадратичная функция может быть не выпуклой (вогнутой), а может быть строго выпуклой (строго вогнутой); все это определяется матрицей D. Элементы матрицы D представляют собой вторые частные производные квадратичной функции, т.е.

Обозначим матрицу вторых частных производных через .

Для того чтобы квадратичная функция была выпуклой (вогнутой) на всем пространстве , необходимо и достаточно, чтобы матрица D была положительно (отрицательно) определена. Если D положительно (отрицательно) определена, т.е.

то строго выпукла (строго вогнута).

Задача максимизации (минимизации) квадратичной функции при линейных ограничениях, где D – отрицательно (положительно) определенная матрица, причем D T =D, называется задачей квадратичного программирования.

Из леммы вытекает, что рассмотренная в разделе 2 задача линейного программирования, как и задача квадратичного программирования, представляет собой частный случай задачи выпуклого программирования.

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

(О существовании седловой точки у вогнуто-выпуклой функции). Пусть X и Y суть выпуклые замкнутые ограниченные подмножества конечномерных евклидовых пространств, а функция – непрерывна по и , вогнута по и выпукла по , тогда имеет на седловую точку.

Рассмотрим функцию Лагранжа для задачи выпуклого программирования:

определенную на прямом произведении , где . Эта функция в силу вогнутости , является вогнутой по и линейной, а следовательно, выпуклой по .

Однако нельзя утверждать на основании теоремы 1, что она имеет седловую точку, так как множество R не обязательно является замкнутым и ограниченным, а Y заведомо неограниченно. Тем не менее, можно ожидать, что при некоторых условиях седловая точка все же будет существовать.

Наиболее известной теоремой, относящейся к этому вопросу, является теорема Куна-Таккера, которая устанавливает связь между существованием решения задачи выпуклого программирования и седловой точки у функции Лагранжа при выполнении условия Слейтера: задача выпуклого программирования удовлетворяет условию Слейтера, если существует такая точка , что выполняется условие: .

Если задача выпуклого программирования удовлетворяет условию Слейтера, то необходимым и достаточным условием оптимальности плана является существование такого , что пара является седловой точкой функции Лагранжа (3.15) на .

То, что условие Слейтера является существенным, показывает следующий пример.

Дана задача выпуклого программирования:

Здесь, очевидно, что x = 0 есть решение задачи, но у функции Лагранжа седловой точки нет, так как внешняя грань в минимаксной задаче не достигается:

Разбиение ограничений в задаче выпуклого программирования на и , как уже говорилось, является условным. Поэтому обычно под R понимается множество простого вида, это либо все пространство E_n, либо неотрицательный ортант, либо параллелепипед. Сложность же задачи выпуклого программирования определяется системой ограничений:

Так как седловая точка функции Лагранжа ищется на произведении множеств , где Y также является множеством простого вида (неотрицательным ортантом), то смысл теоремы Куна-Таккера состоит в сведении задачи поиска экстремума функции со сложными ограничениями на переменные к задаче поиска экстремума новой функции с простыми ограничениями.

Если множество R совпадает с E_n, то условия экстремума, как известно, имеют вид:

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

Для того чтобы непрерывно дифференцируемая вогнутая функция имела в точке максимум на E_n, необходимо и достаточно, чтобы градиент функции в точке был равен нулю, т.е. .

Вспомним, что градиент функции равен:

Таким образом, для нахождения седловой точки функции Лагранжа на произведении , а следовательно, и для нахождения решения задачи выпуклого программирования при R=E_n надо решить систему уравнений (3.16). Но в этой системе n уравнений, а неизвестных n+m, так как помимо n-мерного вектора нам неизвестен и m-мерный вектор множителей Лагранжа . Однако для седловой точки функции Лагранжа выполняется очень важное свойство:

Из уравнения (3.17) вытекает, что либо , либо , либо то и другое одновременно. Это свойство аналогично второй теореме двойственности (подразд. 2.5) линейного программирования. Ограничения, которые выполняются в некоторой точке как равенства, называются активными.

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

Это множество представляет собой совокупность индексов активных в точке ограничений. Тогда можно утверждать в силу сказанного выше, что . Поэтому для определения и ненулевых имеем систему уравнений:

Число неизвестных и число уравнений в этой системе совпадают, поэтому, в принципе, находя решение системы (3.18), тем самым решим исходную задачу выпуклого программирования. Система (3.18) представляет собой необходимые и

достаточные условия оптимальности для задачи выпуклого программирования в случае, когда R = E_n.

Если R является неотрицательным ортантом, т.е.

то для каждой компоненты решения задачи выпуклого программирования возможны две альтернативы: либо , либо . Для первой альтернативы условия оптимальности совпадают со случаем R=E_n, т.е. имеют вид (3.16) (при данном j). Для второй альтернативы это не так.

Если является компонентой точки максимума функции по в области , то можно утверждать, что необходимо (а для вогнутой функции и достаточно) только выполнения неравенства

т.е. функция должна не возрастать по при движении внутрь области .

Но так как , то можно записать:

Объединяя обе альтернативы, т.е. учитывая выражения (3.16), (3.19), (3.20) для задачи выпуклого программирования в случае, можно представить в виде

Так как , то из условий (3.21) следует, что либо , либо . Таким образом, как и в случае R=E_n, имеем n уравнений, которые вместе с уравнениями для активных ограничений определяют и .

Найти при ограничении .

Здесь . Функция линейная и поэтому максимум достигается на границе допустимого множества. Используя условия (3.18), имеем систему трех уравнений с тремя неизвестными:

(другое решение дает минимум).

В общем случае, когда R – произвольное выпуклое множество, необходимые и достаточные условия оптимальности для задачи выпуклого программирования формулируются с помощью производных по направлению.