Wednesday, May 16, 2018

Simplex Method and task 18 advanced development

***************************************************************************
Обновление от 01.12.2019
***************************************************************************
Сейчас этот пост имеет 1573 чтений. Примерно 
в 10 раз больше, чем другие посты (реально интересные)
говорит это только об одном
Из басни Крылова
Беда, коль пироги начнет печи сапожник,
А сапоги тачать пирожник,
И дело не пойдет на лад.
Да и примечено стократ,
Что кто за ремесло чужое браться любит.
Тот завсегда других упрямей и вздорней:
Он лучше дело все погубит,
. . . . . . . . .

*************************************************************************

Линейная форма на плоскости достигает обоих экстремумов на любом
выпуклом оганиченном N-угольнике,иными словами справа от А (Досрочный ЕГЭ Информатика 2016 задача 18) может быть добавлено  разумное количество дизъюнкций, каждое из которых будет добавлять
полуплоскость. Отрицание к каждой из скобок будет определять полуплоскость дополняющую указанную в скобке полуплоскость до всей плоскости,а пересечение полуплоскостей (полученных отрицанием ) выпуклый N-угольник. Скобка, содержащая А определяет линейную форму максимум которой нужно определить. Он и будет совпадать с А.

Видео  https://www.youtube.com/watch?v=HEoCopBfU1k



Например : При x >=0 ; y>=0 найти A(min)
(5x+4y<A)v(6x+4y>24)v(x+2y>6)v(y>2)v(y-x>1) = 1
для всех (x,y) на плоскости

Рассмотрим решение приведенного примера симплекс методом
Остается обозначить направляющий вектор целевой формы и провести прямые, перпендикулярные к нему от -infinity to +infinity.




 
Симплекс метод для пространства любой размерности R(n) применен в той
же ситуации. Нетрудно видет, что руками это сделать не просто даже
для модельной задачи
Simplex Method and task 18 for limited number of x1,x2, ,x(n)

No comments:

Post a Comment