Улучшение опорного плана осуществляется путем целенаправленного переноса из клетки в клетку транспортной таблицы отдельных перевозок без нарушения баланса по некоторому замкнутому циклу.
Каждый цикл имеет четное число вершин, одна из которых в клетке с небазисной переменной, другие вершины в клетках с базисными переменными. Клетки отмечаются знаком «+», если перевозки в данной клетке увеличиваются и знаком «–» в противном случае. Цикл начинается и заканчивается на выбранной небазисной переменной и отмечается знаком «+». Далее знаки чередуются.
Количество единиц продукта, перемещаемого из клетки в клетку по циклу, постоянно, поэтому сумма перевозок в каждой строке и в каждом столбце остаются неизменными. Стоимость всего плана изменяется на цену цикла.
Улучшение опорного плана осуществляется путем нахождения цикла с отрицательной ценой.
5. Если критерий оптимальности не выполняется, то переходим к следующему шагу. Для этого:
г) составляется новая таблица, добавляя X в плюсовые клетки и отнимая X из минусовых клеток цикла;
6. Возвращаются к пункту 3 и т.д.
7. Через конечное число шагов (циклов) обязательно приходят к ответу, так как транспортная задача всегда имеет решение.
Задача линейного целочисленного программирования формулируется следующим образом:
принимает максимальное значение при ограничениях: 
Методы целочисленной оптимизации можно разделить на три основные группы:
a. методы отсечения;
b. комбинаторные методы;
c. приближенные методы.
Подробнее остановимся на методах отсечения. Сущность методов отсечения состоит в том, что сначала задача решается без условий целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:
• оно должно быть линейным;
• должно отсекать найденный оптимальный нецелочисленный план;
• не должно отсекать ни одного целочисленного плана.
Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением.
Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.
Один из алгоритмов решения задачи линейного целочисленного программирования, предложенный Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.
Алгоритм метода Гомори:
1. Симплексным методом решается задача (5.1)-(5.3) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования (5.1)-(5.4). Если первая задача (8.1)-(8.3) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и вторая задача (5.1)-(5.4) также неразрешима.
2. Если среди компонент оптимального решения есть нецелые, то выбирают компоненту с наибольшей целой частью и по соответствующему уравнению системы ограничений формируется правильное отсечение:
(5.5)3. Неравенство (5.5) введением дополнительной неотрицательной целочисленной переменной преобразовывают в равносильное уравнение
(5.6)и включить его в систему ограничений (5.2).
4. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования (5.1)-(5.4) решена. В противном случае возвратиться к пункту 2.
Если задача разрешима в целых числах, то после конечного числа шагов (итераций) оптимальный целочисленный план будет найден.
Задачи экономической науки, требующие применения математики
Имеется ряд определений предмета экономической теории. Из них вытекает необходимость экономико-математических методов, причем требуется самая изощренная современная математика, как теоретическая, так и прикладная. Фактически существует такая дисциплина, как математическая экономика, которая у ряда авторов представляет собой чисто математическую теорию с типичным для нее построением: формальные определения с соответствующими примерами реальных объектов, затем теоремы, их точные доказательства, интерпретация этих теорем. Такой способ построения экономической теории напоминает о некоторых реализациях такой дисциплины, как математическая физика, в виде чисто математической абстрактной теории. Все это крайности, которые необходимы для интенсивного развития математического аппарата, но они должны быть лишь частью теории, служащей некоторым содержательным, жизненно необходимым и в конечном счеты неформализуемым задачам.
Определения экономической теории, синтезированные из работ ряда авторов (таких, как Э.Маленво, П.Самуэльсон, Г.Саймон, И.Экланд):
Экономическая теория — это наука, которая:
Во-первых, изучает проблемы наилучшего использования ограниченных возможностей человеческой деятельности.
Но так как люди редко действуют рационально и эффективно, то:
Во-вторых, она изучает РЕАЛЬНОЕ поведение человека, который В ПРИНЦИПЕ умеет связывать экономические цели и средства их достижения.
Дальше идёт конкретизация:
В-третьих, она изучает, как ограниченные ресурсы используются для удовлетворения потребностей людей, живущих в обществе. И потому предмет её исследований — это основные экономические процессы, такие, как производство, распределение благ и их потребление. С другой стороны, экономическая теория изучает институциональные структуры и процессы, преследующие цель организации упорядоченного прохождения этих операций и процессов.
В-четвёртых, экономическая теория описывает и изучает человеческий выбор, в том числе — обмен в условиях ограничений. Ограниченные ресурсы, которые здесь существенны — это материальные, трудовые, финансовые, технологические, информационные и другие. Информационная сторона экономических процессов становится все более важной, в связи с чем все большее значение приобретает экономическая информатика.
В-пятых, теория изучает, как из индивидуальных способов поведения, рассматриваемых, как исходные, как заданные, выводятся закономерности на уровне общества; как индивидуальные решения синтезируются в коллективные.
При этом следует сказать, что экономическая теория может быть как дескриптивной, так и нормативной.
Дескриптивная - описательная - экономическая теория описывает поведение людей при выборе экономических действий (на основе оценок текущего состояния, его диагностики и прогнозирования его развития).
Нормативная теория даёт рекомендации по оптимальному экономическому поведению.
Таким образом, в абстрактной форме основные задачи экономики суть математические задачи выбора и диагностики (сюда включаются и прогнозирование, и оценки ситуаций), усложнённые неформализованными элементами, противоречивыми, сингулярными моделями и т.д.
Математика в экономической науке, в экономической информатике применяется во все больших масштабах. Сейчас очевидно, что она — необходимая часть экономической теории. Однако она недостаточна, так как и чисто экономическая содержательная составляющая становится все более сложной, а неформализованная сторона описания экономических явлений всегда будет присутствовать.
И существует не только рациональный выбор индивидуумами их решений, который есть предмет неоклассической экономической теории. Рациональное целесообразное поведение ограничено в своих возможностях — с точки зрения ресурсов, организационных возможностей, степени охвата разнообразных, разноплановых, в том числе и неформализованных, связей, с точки зрения возможности учёта традиций, психологии и так далее.
Оно ограничено также потенциалом вычислительных средств для вычисления эффективного поведения и учёта поведения других субъектов. Это и требует дополнения неклассической теории (основанной на принципах целесообразного поведения) другими средствами моделирования. Неоклассическая теория базируется на концепции выбора из множества альтернатив с использованием функции полезности.
Но это нужно дополнить средствами решения таких проблем:
1. как обнаруживать и записывать эти альтернативы, их множество и способы выбора из них;
2. как описывать и идентифицировать функцию полезности или отношения предпочтения;
3. Как связывать альтернативы, полезности, действия, выбора и реализации альтернатив (причем и чисто эмпирические реализации);
4. как учитывать реальную и нормативную рациональную эмпирику;
5. как учитывать ограничения на передачу информации (скорость, объемы) и на вычислительную сложность.
имеет максимальное значение;
(5.1)