Решение:

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

4.

В каких случаях необходимо решать задачу целочисленного программирования? Что необходимо предпринять для обеспечения решения такой задачи?

Решение:

В экономике существует огромное количество задач с целочисленной природой. Прежде всего это задачи с физической неделимостью многих факторов и объектов расчета. Например, нельзя построить 3,2 завода или поставить 1,6 автомобиля. Количество комплектов, число агрегатов, число типовых размеров предприятий, типовые мощности предприятий — все это вносит целочисленность в оптимизационные расчеты. целочисленными являются задачи с логическими переменными, принимающими только два значения — нуль или единица (вариант отвергается или принимается).

В первом приближении методы целочисленной оптимизации можно разделить на две основные группы: точные и приближенные. К точным относятся методы отсечения и комбинаторные (метод ветвей и границ). Это универсальные методы дискретной оптимизации. Кроме универсальных, имеется много специальных точных методов, учитывающих специфику задачи. Однако точные методы имеют слабую сходимость. Многие экспериментальные и прикладные задачи не удалось решить точными методами за десятки и сотни тысяч итераций, хотя их конечность теоретически доказана. Трудности машинной реализации точных методов привели к появлению различного рода приближенных, построенных на использовании особенностей конкретной задачи. Среди приближенных методов наметились два направления: 1) разработка детерминированных эвристических алгоритмов, учитывающих специфику задачи; 2) использование случайного поиска в сочетании с локальной оптимизацией.

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

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

5.

Что такое точка перегиба и как ее идентифицировать?

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

Необходимое условие существования точки перегиба: если – точка перегиба графика функции , то при вторая производная равна нулю или не существует.

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

6.

Дана задача:

Найти графическое решение задачи.