II. 4.4. Некоторые рекомендации по формулировке и решению задач ЦЛП

1. Количество целочисленных переменных следует уменьшить на сколько это возможно.

2. По возможности получить “близкие” друг другу верхнюю и нижнюю границы.

3. Чем больше ограничений, тем меньше время обработки задачи и ее решения.

4. Можно допускать погрешность:

5. Ветвление в порядке приоритетов.

В качестве упражнений, выполните задания п. II.2. Заметим, что эти задачи ввиду своей малой размерности позволяют выполнить вычисления вручную. Однако мы рекомендуем для расчетов дополнительно использовать вычислительную технику, например, вычислительные средства пакета прикладных программ “научного менеджмента” QSB.

[1] оптимальное значение характеристического показателя совпадает с экстремумом.

[2] с достаточной степенью достоверности.

[3] проведение экспериментов даже с моделью требует осмысленных действий. В последнее время с бурным развитием ЭВМ и появлением массы прикладных программ, возникла тенденция бессистемного привлечения вычислительных средств. Исследователь, не замечая за деревьями леса, блуждает в потемках, не делая при этом ни правильных посылок, ни правильных выводов.

[4] Здесь выделяют подкласс задач целочисленного программирования, где в дополнение всего, переменные целые.

[5] Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую линейную комбинацию (линейную оболочку).

[6] Две граничные точки некоторого отрезка, состоящего из граничных точек ОДР, называются крайними. Точка называется граничной для некоторого множества точек, если для любого сколь угодно малого в окрестности ее находятся и точки множества, и точки ему не принадлежащие.

[7] Будем обозначать их или кратко.

[8] Соседняя вершина ОДР – смежное допустимое решение.

[9] Количество линейно независимых строк или столбцов матрицы. Напомним, что существует и другое определение ранга матрицы (тоже и линейного оператора) - это порядок ее базисного минора.

[10] Здесь важно отметить, что это далеко не единственный метод. Существует ряд других методов, например, метод дифференциальных рент или метод минимального элемента (которые, вместе с методом северо-западного угла, являются наиболее употребляемыми при решении транспортных задач) и другие.

[11] Ломаная линия с вершинами в отмеченных (базисных) клетках плана перевозок.

[12] Нумерация элементов цепочки начинается с элемента, соответствующего максимальному по абсолютной величине отрицательному элементу оценочной матрицы.

[13] Не нарушая общности рассуждений, для определенности будем предполагать, что все ограничения задачи – ограничения типа неравенств, и в системе ограничений рассматриваемой задачи они ориентированы.

[14] Для удобства записи, здесь симплекс-таблицы записываются в несколько ином виде, что принципиально несущественно.

[15] Здесь умышленно рассматривается случай двух переменных, для того чтобы не обременять решение задачи излишними математическими выкладками, связанными с применением симплекс-метода.

[16] В самом деле, целочисленная точка является внутренней точкой ОДР исходной задачи и для того, чтобы попасть в нее необходимо осуществить движение в направлении обратном, что приведет к уменьшению значения целевой функции.

Поиск по сайту: