5. Задача о смесях (о диете, о рационе) 4
Скачать 0.53 Mb.
|
| ^ Две группы: 1. барьерные 2. штрафные В общем случае под градиентными методами понимают методы, в которых направления движения к точке оптимума функции совпадают с направлением градиента этой функции. Используя градиентные методы, можно найти решение любой ЗНЛП. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач выпуклого программирования, в которых всякий локальный экстремум является одновременно и глобальным. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что начиная с некоторой точки X(k) осуществляется последовательный переход к некоторым точкам до тех пор, пока не выявляется приемлемое решение исходной задачи. ^ Итак, процесс нахождения решения задачи методом Франка-Вулфа включает следующие этапы: 1. Определяют исходные допустимые решения задачи. 2. Находят градиент функции в точке допустимого решения. 3. Строят функцию и находят ее максимальное значение при условиях 4. Определяют шаг вычислений. 5. По формулам находят компоненты нового допустимого решения. 6. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи. ^ процесс нахождения решения задачи выпуклого программирования методом штрафных функций включает следующие этапы: 1. Определяют исходное допустимое решение. 2. Выбирают шаг вычислений. 3. Находят по всем переменным частные производные от целевой функции и функций, определяющих ОДР задачи. 4. По формуле  находят координаты точки, определяющей возможное новое решение задачи.5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу. Если координаты найденной точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему допустимому решению. В случае такой необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи. 6. Устанавливают значения весовых коэффициентов и переходят к этапу 4. ^ 1. выбирают любую точку X0, удовлетворяющую области решений (в дальнейшем эта точка Xk) 2. Находят частные производные, а затем градиент функции в точке. 3. определяют шаг лямбда 4.по формулам 1. Xk+1= Xk+”лямбда”*1 и 2. Xk+1= Xk+”лямбда”*”обратная дельта’Z(Xk) находят точку Xk+1 5. проверяют, находиться ли точка Xk+1 внутри области решений. 6. проверяют, точку Xk+1 на оптимальность. Если точка не является оптимальным решением повторяют пункты 2-6 ^ Класс ЗНЛП значительно шире класса задач линейного программирования. Основные результаты в нелинейном программировании получены при рассмотрении задач, в которых система ограничений линейная, а целевая функция нелинейная. Даже в таких задачах оптимальное решение может быть найдено только для узкого класса целевых функций. частные случаи, когда целевая функция сепарабельная (является суммой n функций fj (xj)) ^ При определении оптимального плана методом аппроксимации Фогеля на каждой итерации по всем столбцам и всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или столбце), которой данная разность соответствует, определяют на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке). ^ Среди практически важных задач отыскания условного экстремума линейной функции важное место занимают задачи с требованием целочисленности всех (части) переменных. Они получили название задач целочисленного (частично целочисленного) программирования. Задача о ранце. Имеется m ограниченных ресурсов b=(b1, b2, …, bm), которые можно использовать для перевозки различных по своим характеристикам грузов. Каждый j-й груз (j=1, 2, …, n) характеризуется следующими свойствами:
Требуется выбрать такой набор груза для перевозки, при котором максимизируется общая полезность рейса. При этом полезность рейса будем определять как суммарную стоимость перевезенных за рейс грузов. Обозначим через xj — количество выбранных для транспортировки предметов и запишем математическую модель этой задачи. Очевидно, требованию неделимости соответствует условие: xj0, xj — целые, j=1, 2, …, n. (1) Сопоставление расхода ресурсов каждого типа для транспортировки единицы груза и наличия ресурсов приводит к ограничению  (2)Общую полезность рейса определяет значение функции  (3)Частным случаем задачи (1—3) является задача о ранце, в которой любой из заданного набора предметов j=1, 2, … , n может быть выбран или нет, т.е. для каждого из xj допустимыми значениями является 0 (предмет не выбирается) или 1 (предмет выбирается). Это приводит к тому, что условие (1) задачи (1—3) заменяется требованием  , (1’)и математическая модель принимает вид: в области, заданной условиями  определить такие составляющие вектора решения x=(x1, x2, … , xn), которые максимизируют функцию  Известно, что дискретная величина, принимающая лишь значения 0 или 1, называется булевой. Поэтому задачи, в которых на переменные накладывается условие вида (1’), получили название задач с булевыми переменными. ^ Такие задачи возникают при минимизации себестоимости    Геометр. : Линии уровня в ЗДЛП образуют семейство прямых проходящих через начало координат, отличающихся углом наклона. Оптимальное решение такой задачи всегда лежит в одной из вершин на грани. ^ решения задачи линейного программирования при изменении ее коэффициентов и свободных членов. Исследования подобного рода и составляют предмет параметрического программирования. Параметрическое программирование возникло в связи с изучением задач планирования производства и дает возможность управлять оптимальным планированием различных экономических процессов, которые могут быть описаны линейной математической моделью. Задачи линейного программирования бывают двух типов: а) задачи с параметром в целевой функции;
б) задачи с параметром в системе линейных ограничений; 1.Считая значение параметра  равным некоторому числу  , находят оптимальный план X* или устанавливают неразрешимость полученной задачи линейного программирования.2. Находят значения параметра  , для которых задача имеет один и тот же план или неразрешима. Эти значения параметра исключают из рассмотрения.3.Выбирают значение параметра из оставшейся части промежутка  и устанавливают возможность определения нового оптимального плана. В случае существования оптимального плана находят его двойственным симплекс-методом.4. Определяют множество значений параметра , для которых задача имеет один и тот же новый оптимальный план или неразрешима. Вычисления проводят до тех пор, пока не будут исследованы все значения параметра .^ параметры целевой функции и (или) системы ограничений изменяются во времени, то такие задачи решаются методами динамического программирования (ДП). Методами ДП могут решаться задачи перспективного и текущего планирования, управления производством, поставками и запасами в условиях изменяющегося спроса, распределения ограниченных ресурсов. 3 типа задач: 1. о замене оборудования 2.о распределение инвестиций 3. задача о ранце ^ параметры целевой функции и (или) системы ограничений изменяются во времени, то такие задачи решаются методами динамического программирования (ДП). Методами ДП могут решаться задачи перспективного и текущего планирования, управления производством, поставками и запасами в условиях изменяющегося спроса, распределения ограниченных ресурсов. 3 типа задач: 1. о замене оборудования 2.о распределение инвестиций 3. задача о ранце ^ 1. принцип отсутствия последствия  Каждый следующий шаг зависит только от преведушего 2.принцип аддитивности целевой функции  Если оба принципа выполняются то можно применить принцип оптимальномсти Беллмана: Пусть U*=(U1*+U2*…….Un*) – выбор оптимальных уранений, который переводит систему из состояния X0 в положение Xn за n шагов., так что целевая функция достигала своего максимального значения. Каково бы ни было состояние системы перед очередным шагом, выбирать уравнение на этом шаге нужно так что бы выигрыш на данном шаге плюс минимальный выигрыш был оптимальным. 70. Связь проблемы выбора с задачами ЛП, НЛП, ИГР |
для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключают из рассмотрения .
, и симплексным методом находят решение полученной задачи линейного программирования.Похожие:
 | Впищевом рационе стали преобладать рафинированные продукты, резко возросло потребление продуктов животного происхождения и снизилась... | | Самое мягкое и эффективное средство- это,конечно, кальций и белок в рационе, в достаточных количествах; Но так же есть еще пара хитрых... |
| Сотни тысяч трудящихся посвящают свой досуг и отдых этому увлекательному и здоровому занятию, добывая огромное количество дичи, которая... | | Знать, что Вы хотите от жизни — это Ваша задача. Показать вам, как Вы сможете всего этого достичь с помощью Сетевого маркетинга —... |
| Знать, что Вы хотите от жизни — это Ваша задача. Показать вам, как Вы сможете всего этого достичь с помощью Сетевого маркетинга —... | | Советуем вам добавить эти 14 продуктов питания к вашему меню и стандартному набору пищевых добавок |
| Задача Доказать, что уравнение m2 + 1978 = n2 не имеет решений в целых числах | | Задача в резервуар залито 20 м3 нефти плотностью 850 кг/м3 и 25 м3 нефти плотностью 840 кг/ Определить плотность смеси |
| Транспортная задача: Методические указания студентам направления 100700 «Торговое дело»/ тгсха; Автор-сост. С. М. Каюгина. – Тюмень,... | | Калифорнии. С профессиональной точки зрения меня всегда восхищала эта женщина, и любой факт из ее жизни обращал на себя внимание.... |