Шпаргалка по дисциплине «Основы математического моделирования социально – экономических процессов»

1.Моделирование: сущность, виды, практические аспекты применения

Моделирование – тот процесс, метод, который позволяет осуществлять перенос информации от реальной системы к модели и наоборот. Моделирование — это универсальный метод получения, описания и использования знаний. Оно используется в любой профессиональной деятельности.

В современной науке и технологии математическое моделирование усиливается, актуализируется проблемами, успехами других наук. Математическое моделирование реальных и нелинейных систем живой и неживой природы позволяет перекидывать мостики между нашими знаниями и реальными системами, процессами, в том числе и мыслительными.

Моделирование - процесс построения, изучения и применения моделей.

Т. е. можно сказать, что моделировaние - это изучение объектa путем построения и исследования его модели, осуществляемое с определенной целью и состоит в зaмене экспериментa с оригинaлом экспериментом нa модели.

Приведем наиболее важные типы моделей (моделирования) с краткими определениями, примерами.

Сущность моделирования.

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

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

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

По уровню агрегирования все известные модели можно разделить на:

-метамодели (блоки сельского хозяйства  и продовольствия в моделях  глобального развития);

-макромодели (рациональные модели  сельского хозяйства и пищевой  промышленности);

-региональные модели;

-многопродуктовые модели;

-модели продуктовых подкомплексов;

-модели агропромышленных формирований  и специализированных предприятий;

-модели отдельных социально-экономических  процессов и явлений.

Виды моделирования.

   Модель называется статической, если среди параметров, участвующих в описании модели, нет временного параметра.

   Модель непрерывная, если она описывает поведение системы для всех моментов времени из некоторого промежутка.

   Модель имитационная, если она предназначена для испытания или изучения, проигрывания возможных путей развития и поведения объекта путем варьирования некоторых или всех параметров модели.

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

   Модель теоретико-множественная, если представима с помощью некоторых множеств и отношений принадлежности им и между ними.

   Модель логическая, если она представима предикатами, логическими функциями.

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

   Модель алгоритмическая, если она описана некоторым алгоритмом или комплексом алгоритмов, определяющим ее функционирование, развитие.

   Модель языковая, лингвистическая, если она представлена некоторым лингвистическим объектом, формализованной языковой системой или структурой.

   Модель визуальная, если она позволяет визуализировать отношения и связи моделируемой системы, особенно в динамике.

   Модель натурная, если она есть материальная копия объекта моделирования.

   Модель геометрическая, графическая, если она представима геометрическими образами и объектами.

2.Модель: понятие и  классификация

Модель – результат отображения одной структуры на другую. Отобразив физическую систему (объект) на математическую систему (например, математический аппарат уравнений), получим физико-математическую модель системы, или математическую модель физической системы. Модель – это тот объект, та система, которая позволяет облечь эту информацию в конкретное, например компьютерное, представление, содержание.

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

Различают физическое и математическое моделирование.

Классификация моделей.

функционально-физические. Предназначены для изучения физических (реальных) явлений, используемых для реализации заложенных в систему функций;

модели процессов и явлений, такие как кинематические, прочностные, динамические и другие. Предназначены для исследования тех или иных свойств и характеристик системы, обеспечивающих её эффективное функционирование.

По особенностям представления

С целью подчеркнуть отличительную особенность модели их подразделяют на простые и сложные, однородные и неоднородные, открытые и закрытые, статические и динамические, вероятностные и детерминированные и т. д. Стоит отметить, что когда говорят, например, о техническом устройстве как простом или сложном, закрытом или открытом и т. п., в действительности подразумевают не само устройство, а возможный вид его модели, таким образом подчеркивая особенность состава или условий работы.

Четкого правила разделения моделей на сложные и простые не существует. Обычно признаком сложных моделей служит многообразие выполняемых функций, большое число составных частей, разветвленный характер связей, тесная взаимосвязь с внешней средой, наличие элементов случайности, изменчивость во времени и другие. Понятие сложности системы — субъективно и определяется необходимыми для его исследования затратами времени и средств, потребным уровнем квалификации, то есть зависит от конкретного случая и конкретного специалиста.

Разделение систем на однородные и неоднородные проводится в соответствии с заранее выбранным признаком: используемые физические явления, материалы, формы и т. д. При этом одна и та же модель при разных подходах может быть и однородной, и неоднородной. Так, велосипед — однородное механическое устройство, поскольку использует механические способы передачи движения, но неоднородное по типам материалов, из которых изготовлены отдельные части (резиновая шина, стальная рама, пластиковое седло).

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

Динамические модели, в отличие от статических, находятся в постоянном развитии, их состояние и характеристики изменяются в процессе работы и с течением времени.

Характеристики вероятностных (иными словами, стохастических) моделей случайным образом распределяются в пространстве или меняются во времени. Это является следствием как случайного распределения свойств материалов, геометрических размеров и форм объекта, так и случайного характера воздействия внешних нагрузок и условий. Характеристики детерминированных моделей заранее известны и точно предсказуемы.

3.Этапы практического  моделирования

Цепочка выглядит следующим образом:

Прототип (объект, процесс) → Моделирование → Принятие решения

Моделирование — творческий процесс. Заключить его в формальные рамки очень трудно. В наиболее общем виде его можно представить поэтапно. При решении конкретной задачи эта схема может подвергаться некоторым изменениям: какой-то блок будет убран или усовершенствован, какой-то — добавлен

Этап 1. Постановка задачи.

Под задачей понимается некая проблема, которую надо решить. На этапе постановки задачи необходимо:

1.  описать задачу,

2.  определить цели моделирования,

3.  проанализировать объект или процесс.

Описание задачи. Главное здесь — определить объект моделирования и понять, что должен представлять собой результат.

Цели моделирования.

1.  Познание окружающего мира. 

2.  Создание объектов с заданными свойствами

3.  Определение последствий воздействия на объект и принятие правильного решения 

4.  Эффективность управления объектом (или процессом). Анализ объекта.

Этап 2. Разработка модели.

Информационная модель. На этом этапе выясняются свойства, состояния, действия и другие характеристики элементарных объектов в любой форме: устно, в виде схем, таблиц. Формируется представление об элементарных объектах, составляющих исходный объект, т. е. информационная модель. Модели должны отражать наиболее существенные признаки, свойства, состояния и отношения объектов предметного мира. Именно они дают полную информацию об объекте. Информации не обязательно должно быть много. Важно, чтобы она была «по существу вопроса», т. е. соответствовала цели, для которой используется.

Выбор наиболее существенной информации при создании информационной модели и сложность этой модели обусловлены целью моделирования.

Построение информационной модели является отправным пунктом этапа разработки модели.

модели в соответствии с целью моделирования.

Знаковая модель

Компьютерная модель — это модель, реализованная средствами программной среды.

Основные функции компьютера при моделировании систем:

·  исполнение роли вспомогательного средства для решения задач, решаемых и обычными вычислительными средствами, алгоритмами, технологиями;

·  исполнение роли средства постановки и решения новых задач, не решаемых традиционными средствами, алгоритмами, технологиями;

·  исполнение роли средства конструирования компьютерных обучающих и моделирующих сред типа: ·  исполнение роли средства моделирования для получения новых знаний;

·  «обучение» новых моделей (самообучение моделей).

Этап 3. Компьютерный эксперимент.

Компьютерное моделирование — основа представления знаний в ЭВМ. Компьютерное моделирование для рождения новой информации использует любую информацию, которую можно актуализировать с помощью ЭВМ.

Разновидность компьютерного моделирования — вычислительный эксперимент, т. е. эксперимент, осуществляемый экспериментатором над исследуемой системой или процессом с помощью орудия эксперимента — компьютера, компьютерной среды, технологии.

Вычислительный эксперимент позволяет находить новые закономерности, проверять гипотезы, визуализировать ход событий и т. д.

Этап 4. Анализ результатов моделирования.

Конечная цель моделирования — принятие решения, которое должно быть выработано на основе всестороннего анализа полученных результатов. Этот этап решающий — либо вы продолжаете исследование, либо заканчиваете. Возможно, вам известен ожидаемый результат, тогда необходимо сравнить полученный и ожидаемый результаты. В случае совпадения вы сможете принять решение.

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

4. Оптимальное управление. Вектор оптимального управления экономическими процессами.

Оптимальное управление — это задача проектирования системы, обеспечивающей для заданного объекта управления или процесса закон управления или управляющую последовательность воздействий, обеспечивающих максимум или минимум заданной совокупности критериев качества системы [1].

Для решения задачи оптимального управления строится математическая модель управляемого объекта или процесса, описывающая его поведение с течением времени под влиянием управляющих воздействий и собственного текущего состояния. Математическая модель для задачи оптимального управления включает в себя: формулировку цели управления, выраженную через критерий качества управления; определение дифференциальных или разностных уравнений, описывающих возможные способы движения объекта управления; определение ограничений на используемые ресурсы в виде уравнений или неравенств[2].

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

Если управляемый объект или процесс является детерминированным, то для его описания используются дифференциальные уравнения. Наиболее часто используются обыкновенные дифференциальные уравнения вида  . В более сложных математических моделях (для систем с распределёнными параметрами) для описания объекта используютсядифференциальные уравнения в частных производных. Если управляемый объект является стохастическим, то для его описания используются стохастические дифференциальные уравнения.

Если решение поставленной задачи оптимального управления не является непрерывно зависящим от исходных данных (некорректная задача), то такая задача решается специальными численными методами[4].

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

Реальное поведение объекта или системы всегда отличается от программного вследствие неточности в начальных условиях, неполной информации о внешних возмущениях, действующих на объект, неточности реализации программного управления и т.д. Поэтому для минимизации отклонения поведения объекта от оптимального обычно используется система автоматического регулирования.[6]

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

Вектор оптимального управления – набор тех параметров, которые обеспечивают оптимальную траекторию функционирования данной ЭС. В любой модели (ЭС) имеются ограничения по ресурсам, по фондам и т.д. Поэтому система ограничений W – запись условий в виде уравнений, неравенств, в которых существует единственное оптимальное решение. Совместимость ограничений – обязательное условие разрешимости любой модели. На практике – это запасы ресурсов, сырья, трудовые ресурсы, финансовые ресурсы, др.

«Смягчить ограничение» - значит, получить показатель оптимизации оптимистичным.

«Ужесточить ограничения» - сделать более строгими, значит получить показатель оптимизации пессимистичным.

Ограничения могут встречаться в разных комбинациях.

5. Достаточность системы ограничений.

В экономических системах  (моделях) критерием оптимальности выбирают

параметры, как правило, определяющие наилучшим образом эффективность данной

системы. Такими параметрами могут быть максимальная прибыль и затраты,

минимальное время достижения цели и т.д.

     Вектор оптимального  управления – набор тех параметров, которые

обеспечивают оптимальную траекторию функционирования данной ЭС. В любой модели

(ЭС) имеются ограничения по ресурсам, по фондам и т.д. Поэтому система

ограничений W – запись условий в виде уравнений, неравенств, в которых

существует единственное оптимальное решение. Совместимость ограничений –

обязательное условие разрешимости любой модели. На практике – это запасы

ресурсов, сырья, трудовые ресурсы, финансовые ресурсы, др.

«Смягчить ограничение» - значит, получить показатель оптимизации оптимистичным.

«Ужесточить ограничения» - сделать более строгими, значит получить показатель

оптимизации пессимистичным.

Ограничения могут встречаться в разных комбинациях.

ЭММ линейна тогда и только тогда, когда целевая функция и система ограничений

линейны. Любая комбинация:

-          целевая  функция линейна - W нелинейна;

-          целевая  функция нелинейна - W линейна;

-          целевая  функция нелинейна - W нелинейна;

приводит к нелинейности модели.

6. Матричные экономико-математические модели

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

8. Классификация систем и их моделей. 
В зависимости от признаков системы, сами системы и их модели классифицируются на: 
-динамические и статические; 
-стохастические (вероятностные) и детерминированные (регулярные); 
-непрерывные и дискретные; 
-линейные и нелинейные. 
По наличию обратных связей системы подразделяются на открытые, закрытые, комбинированные. 
 
 
Открытые: 
Закрытые: 
Комбинированные:

9. Особенности экономических систем

Экономическая система является частью более сложной системы – социально-экономической, и представляет собой вероятностную, динамическую, адаптивную систему, охватывающую процессы производства, обмена, распределения и потребления материальных благ, а также предоставления различных сервисных услуг. Как правило, входные параметры экономических систем – это материальные вещественные потоки производственных и природных ресурсов, то есть Х. Входные параметры – это материальные вещественные потоки, оборудование, военная продукция, продукция накопления, возмещения и экспорта, то есть У. 
 
Экономические системы – многоступенчатые, многоуровневые системы, и любая неопределенность, случайность во входных параметрах в нижних уровнях приводит к неопределенностям и случайностям в выходных параметрах подсистем более высокого порядка и системы в целом.   
Структурная схема простой экономической системы 
ЭММ оптимизации обычной экономической системы 

где pi – прибыль от реализации единицы продукции;  
xi - объем выпуска продукции;  
ai - расход сырья на единицу продукции;  
B - общий запас сырья; 
W - область допустимых ограничений;

10.

11.

12.

13. Стандартная задача  линейного программирования Линейное программирование – раздел математического программирования, состоящий в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные. Слово «программирование» объясняется здесь тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно в совокупности определяют программу (план) работы некоторого экономического объекта. Слово «линейное» отражает факт линейной зависимости между переменными. При этом, как указано, задача обязательно имеет экстремальный характер, т. е. состоит в отыскании экстремума (максимума или минимума) целевой функции;

Задачами линейного программирования называются оптимизационные задачи, в которых ограничения, представленные в виде равенств или неравенств, и целевая функция линейна. Разработка модели ЛП включает следующие основные этапы: определение переменных задачи, представление её ограничений в виде линейных уравнений или неравенств, задание линейной целевой функции, подлежащей минимизации или максимизации.

Задача ЛП в стандартной форме с  m ограничениями и n  переменными имеет следующий вид:

максимизировать или минимизировать 

при ограничениях:

.

Задачи ЛП в стандартной форме можно записать в компактных матричных обозначениях следующим образом:

максимизировать или минимизировать 

при ограничениях 

где A - матрица размерности mxn,  x - вектор-столбец  размерности nxl, b- вектор-столбец  размерности mxl, а c - вектор-строка размерности .1xn.

Обычно  A назначается матрицей коэффициентов,  x - вектором переменных,  b - вектором ресурсов, c - вектором оценок задачи ЛП.

При решении задачи ЛП симплекс-методом требуется, чтобы задача была представлена в стандартной форме. Однако не все практические задачи ее имеют, поэтому для удовлетворения требования алгоритма необходимо следующее.

1. При помощи введения дополнительных  остаточных или избыточных переменных  преобразовать неравенства в  равенства.

2. Для получения неотрицательных  переменных задачи неограниченные  по знаку переменные заменить  разностью двух неотрицательных.

При решении задач ЛП используются следующие основные понятия. Допустимым решением являются неотрицательные значения переменных, для которых выполняются ограничения, а допустимой областью - совокупность допустимых решений. Оптимальным решением называются такие допустимые значения переменных, при которых ЦФ экстремальна, т.е. имеет оптимальное значение. В ряде случаев, ЦФ имеет одно оптимальное значение при нескольких комбинаций значений переменных, следовательно, задача обладает неединственностью оптимума. Когда в задаче ЛП нет конечного оптимума, то в этом случае существует неограниченный оптимум.

14. Графический метод решения задач  линейного программирования

Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.

Описание метода

Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные.

Найти минимальное значение функции

при ограничениях вида

и

Допустим, что система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми:  .

Линейная функция (1) при фиксированных значениях   является уравнением прямой линии:  .

Пример графического решения задачи линейного программирования с 6 условиями.

Построим многоугольник решений системы ограничений (2) и график линейной функции (1) при  . Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию:

Найти точку многоугольника решений, в которой прямая   опорная и функция   при этом достигает минимума.

Значения   уменьшаются в направлении вектора  , поэтому прямую   передвигаем параллельно самой себе в направлении вектора  .

Если многоугольник решений ограничен (см. рисунок), то прямая дважды становится опорной по отношению к многоугольнику решений (в точках   и  ), причём минимальное значение принимает в точке  . Координаты точки   находим, решая систему уравнений прямых   и  .

Если же многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая.

Случай 1. Прямая  , передвигаясь в направлении вектора   или противоположно ему, постоянно пересекает многоугольникрешений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.

Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху.

15. Транспортная задача. Критерий оптимальности, постановка задачи

Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. Транспортная задача является одной из наиболее распространенных специальных задач линейного программирования. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О. Н. Толстым. Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Методом потенциалов для каждой строки и каждого столбца рассчитывается потенциал по след. Формуле vj –ui=cij для занятых клеток.

Потенциалы рассчитываются однозначно, для простоты вычисления принимаем величину u1=0.

Проверим задачу на оптимальность. Должно выполняться след. Условие для всех клеток vj-ui>/=cij задача решена.

Из тех клеток, где условие не выполняется выбираем ту где большая разница между правой и левой частью неравенства и строим цикл перерасчёта для каждой свободной клетки цикл строится единственным образом. Цикл перерасчёта представляет собой геометрическую фигуру, где все углы прямые и все остальные вершины, кроме выбранной нами занятыми клетками. Цикл может иметь след. Форму:

В выбранной вершине ставим знак +, затем поочерёдно чередуем +, -

Из вершин с отрицательным знаком выбираем значение наименьшее по модулю и проводим перерасчёт, там где – ту величину вычитаем, там где + ту величину прибавляем.

F(x)=nm+n1m1+n2m2+…..=

Доказано, что за конечное число пересчётов может быть найдено оптимальный вариант решения задачи.

16. Метод потенциалов             

Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90 , Знаком " + " отмечают те вершины, в которых перевозки увеличиваются, а знаком "- " - те вершины, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение перевозок на это же количество единиц в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым. Стоимость плана при этом может меняться.            

Ценой цикла называется увеличение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком " +", а стоимости в отрицательных вершинах берутся со знаком " - ".            

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

Для нахождения циклов с отрицательной ценой вводится система

платежей  

и определяются величины    

называемые "псевдостоимостями" перевозок единицы груза из пункта i

в пункт j.  При этом цена цикла пересчета для каждой свободной клетки

равна       

если платежи            

  для всех базисных клеток (i, j)

9.9 Вычислительная схема  метода потенциалов  [1, 3]            

Шаг 1. Строим опорный план (методом северо-западного угла) с

n+m-1   базисными клетками.            

Шаг 2. Определяем платежи

для всех базисных клеток. Один из платежей (например a1 ) полагаем равньм нулю. 

Шаг 3. Считаем псевдостоимости  

для всех свободных клеток. Если    

для всех клеток, то план оптимален. Вычисляем значение целевой функции L на этом плане и исследования прекращаем.                          

Шаг 4. Если есть свободная клетка, для которой    

то улучшаем план, перебрасывая перевозки по циклу этой свободной клетки. 

Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана. 

17. Метод нахождения опорного плана транспортной задачи.

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:           Базисными клетками транспортной таблицы являются клетки с отличными от нуля положительными перевозками, остальные клетки -  свободные. Базисные клетки образуют опорный план транспортной задачи, если выполняются два условия: 

1) сумма перевозок в каждой  строке равна запасу   в данной

строке; 

2) сумма перевозок в каждом  столбце равна соответствующему

столбцу спросу    

Опорный план транспортной задачи содержит не более n+m-1

отличных от нуля перевозок      

Опорный план называется вырожденным, если число ненулевых перевозок    

меньше и n+m-1, опорный план - невырожден, если число

ненулевых перевозок равно n+m-1.

Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях.

18.