Уважаемый студент!

Стоимость данной работы составляет 300 руб. Если Вас устраивает цена, Вы можете связаться с нами любым удобным для Вас способом:

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

Всегда рады помочь!

Вопрос 1

Описать идею методов отсечений. Понятие отрезка локализации. Каким требованиям должно удовлетворять правило выбора точек измерения в методах отсечений?

Вопрос 2

Необходимые условия безусловного экстремума функции многих переменных. Теорема Вейерштрасса.

Задача 3

Методом проекции градиента решить задачу с точностью 0,1:
F(x) = x1^2+2x2^2-x1x2+4x1-2x2+1->min, 2x1-3x2<= -6


Пример выполнения:

Описать идею методов отсечений. Понятие отрезка локализации. Каким требованиям должно удовлетворять правило выбора точек измерения в методах отсечений?

Ответ.

Методы отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП). Идея методов отсечения состоит в следующем. 
Первоначально решается обычная ("непрерывная") задача ЛП, полученная из исходной задачи отбрасыванием требования целочисленности. Если полученное решение является целочисленным, то оно будет также решением исходной задачи. Если нет, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами: 

- полученное нецелочисленное решение ему не удовлетворяет; 

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

Такое ограничение называется правильным отсечением. Локализация (отделение) решения является одним из основных этапов решения задач. Отрезок, содержащий решение задачи, называется отрезком локализации этого решения. 

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

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

Обозначим через Lk и х(k), k=0,1,..., соответственно k-ю расширенную непрерывную задачу ЛП и ее решение. Отметим, что L0 представляет собой исходную задачу без учета требований целочисленности. Задача Lk+1 получается в результате добавления к ограничениям задачи Lk (k+1)-ro правильного отсечения. 

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

  1. Решается задача ЛП L0.
  2. Если задача L0 не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются.
    Находится решение х(0) . 
  3. Если решение х(0) является целочисленным, то полагается х* = х(0), f *= f (х(0)) и вычисления завершаются.
  4. Если решение х(0) не является целочисленным, то полагается k = 1 и осуществляется переход к п. 3.
  5. Определяется k-е правильное отсечение, составляется задача Lk.
  6. Решается задача ЛП Lk.
  7. Если задача Lk не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются.
    Находится решение х(k). 
  8. Если решение х(k) является целочисленным, то полагается х* = х(k), f * = f (х(k)) и вычисления завершаются.
  9. Если решение х(k) не является целочисленным, то полагается k = k +1 и осуществляется переход к п. 3.

Внимание! На сайте представлен не полный ответ на вопрос!


22 стр.