2 Алгоритм решения транспортной задачи.

Алгоритм решения задачи. 1. составим ЭММ задачи, 2. проверить задачу на сбалансированность и при необходимости привести к сбалансированному виду. 3. получить опорное решение заданным способом: метод северо-западного угла, метод наименьшего (наибольшего) члена, метод аппроксимации, метод предпочтений. 4. решить задачу методом потенциалов. Он состоит из последовательности итераций и шагов. Шаг 1. выписать исходное базисное решение, проверяем план на вырожденность. Если план вырожденный, то вводим в 1 из пустых клеток нулевую поставку и считаем эту клетку занятой, при этом данная клетка не должна приводить к замкнутому контуру занятых клеток. Шаг 2. проверяем план на оптимальность. Если план не оптимален, то переходим к шагу 3. если план оптимален, то переходим к пятому этапу. Шаг 3. выполняю процесс улучшения плана. Шаг 4. строим новый план перевозок.

Билет4

1.Предмет, метод и задачи курса.

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

2. Методы построения опорного плана при решении транспортной задачи лп.

Алгоритм решения задачи. 1. составим ЭММ задачи, 2. проверить задачу на сбалансированность и при необходимости привести к сбалансированному виду. 3. получить опорное решение заданным способом: метод северо-западного угла, метод наименьшего (наибольшего) члена, метод аппроксимации, метод предпочтений. 4. решить задачу методом потенциалов. Он состоит из последовательности итераций и шагов. Шаг 1. выписатьисходное

базисное решение, проверяем план на вырожденность. Если план вырожденный, то вводим в 1 из пустых клеток нулевую поставку и считаем эту клетку занятой, при этом данная клетка не должна приводить к замкнутому контуру занятых клеток. Шаг 2. проверяем план на оптимальность. Если план не оптимален, то переходим к шагу 3. если план оптимален, то переходим к пятому этапу. Шаг 3. выполняю процесс улучшения плана. Шаг 4. строим новый план перевозок.

Билет 4

1.  Предмет курса – количественной характеристики экономических процессов, протекающих в с-х, ЗУ-ве, их взаимосвязи, основной метод которого – метод моделирования. Задача курса – научиться применять математическое моделирование в ЗУ-ве, освоить пакеты прикладных программ для решения задач программирования, научиться проводить экономический и ЭМ  анализ оптимальных решений.

 

2. Теорема о разрешимости транспортной задачи. Сведение задачи открытого типа к задаче закрытого типа

Транспортную задачу, в которой имеется равенство сумма от i=1 до m а_i= сумме от j=1 до n в_j называют закрытой, если равенство не выполняется, то задача открытая. Чтобы решить задачу, необходимо ее сбалансировать, т.е. привести к закрытому виду.  Если первая часть больше второй части равенства, то вводится фиктивный потребитель в_n+1 с потребностью в_n+1=пеовая часть равенства минус вторая. В таблице добавляется столбец. Если наоборот, то вводим фиктивного поставщика Аm+1 c наличием груза аm+1= вторая часть неравенства минус первая. В таблице добавляется строка.

Билет  5

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

2.  1. Составить экономико-математическую модель задачи. 2. Проверить задачу на сбалансированность и, при необходимости, привести к сбалансированному виду.3. Получить опорное решение заданным способом: метод северо-западного угла, метод наименьшего (наибольшего) члена, метод аппроксимации, метод предпочтений (процесс решения отразить в таблице).4. Решить  задачу методом потенциалов  (процесс решения отразить в таблицах). Метод потенциалов состоит из последовательности итераций и шагов.ШАГ 1. Выписываю исходное базисное решение. Проверяем план на вырожденность. Если план вырожденный, то вводим в одну из пустых клеток поместить нулевую подставку и считать эту клетку занятой, при этом данная клетка не должна приводить к замкнутому контуру и занятых клеток. ШАГ 2. Проверяю план на оптимальность. Если план не оптимален, то переходим к шагу 3, если план оптимален, то переходим к 5 этапу. ШАГ 3.  Выполняю процесс улучшения плана. Шаг 4. Строю новый план перевозок. 5. Записать решение формализовано поставленной задачи, и дать его интерпретацию с учетом дополнительных условий (при их наличии) и исходной несбалансированности задачи (если она была), после чего записать окончательное решение задачи.

Билет 6 Основные элементы базовой экономико-математической модели.

 

1.  Основные элементы базовой ЭММ. Переменные – это неизвестные величины, значение которых находится в процессе решения задач. Для каждой переменной устанавливают определенную, конкретную единицу измерений. Ограничения- это математические зависимости, отражающие условия реализации задач, требования, накладываемые на переменные. Ограничения записываются 3 видами отношений >,=,<. Целевая функция- это записанные в математическом виде критерии оптимальности. Критерии оптимальности- это показатель, отражающий реализацию поставленной цели. Решение (план) – это набор значений неизвестных. Допустимое решение (допустимый план)- это набор значений неизвестных, удовлетворяющих ограничениям. Все допустимые решения образуют область определения задач линейного программирования (область допустимых решений). Базисное решение- это набор значений неизвестных, соответствующих угловых точек многоугольника (многогранника). Оптимальное решение- набор переменных, удовлетворяющих ограничению и максимизирующихили минимизирующих целевую функцию.

2 1. Выбираем m переменных, задающих допустимое пробное решение и исключим эти переменные из целевой функции.2. Проверяем нельзя ли за счет одной из переменных приравненной к нулю (небазисной), улучшить значение целевой функции, придавая ей отличные от нуля значения. Если это, возможно, перейдем к третьему этапу, в противном случае прекратим вычисления. 3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из m переменных, вошедших в пробное решение не обратится в нуль.4. Разрешим систему из n уравнений относительно переменной, вошедшей в новое пробное решение. Вернемся ко второму этапу.

Билет 7 Типы, виды и классы математических моделей, применяемых в землеустройстве.

 

1. Все модели можно условно разделить на 2 класса: 1. физические и 2. абстрактные. Физические модели – строятся на принципах аналогии, т.е. оригинал и модель могут отличаться лишь несколькими параметрами. Абстрактная модель – это модель, описывает поведение системы абстрактно-логическими средствами, это могут быть числовые модели, знаковые, графические и т.д. большое место среди абстрактных моделей занимают математические модели. В них закономерности поведения системы описывается в виде уравнений, неравенств, функций. Среди математических моделей важное место занимает ЭММ, они представляют собой математическое описание экономических процессов и явлений. Большой класс в ЭММ, применяемых на практике, занимают так называемые оптимизационные модели –это такие модели, которые при определенных данных допускают получение множества решений, удовлетворяющих условиям задачи и обеспечивает выбор оптимального решения, отвечающего критерию оптимальности. В ЭММ применяются различные виды линейных и не линейных математических зависимостей, хотя зависимости в экономике носят преимущественно не линейный характер, мы будем предполагать, что большинство не линейных зависимостей могут в достаточной степени точности описываться в виде линейных зависимостей, т.е. мы можем предположить что все зависимости линейные.

2. Метод потенциалов состоит из последовательности итераций и шагов.

Билет 8 Основные этапы моделирования.

 

1. Развитие экономико-математических исследований в земле­устройстве можно разделить на три этапа. На первом этапе, который длился с начала 60-х до конца 70-х годов, были обоснованы необходимость и возможность приме­нения экономико-математических методов и моделей в земле­устройстве. В это время были сформулированы основные эко­номико-математические задачи. В качестве базовых использовали методы линейного программирования (транспор­тная задача, решаемая методом потенциалов, а также сим­плекс-метод). Начали применяться также приемы динамичес­кого, параметрического, целочисленного и стохастического программирования. На первом этапе моделировались и решались в основном за­дачи проектов внутрихозяйственного землеустройства. Второй этап внедрения экономико-математических методов и моделирования в землеустройстве относится к 80-м годам; он связан с обоснованием и созданием автоматизированных сис­тем плановых расчетов (АСПР), систем автоматизированного проектирования (САПР), разного рода автоматизированных ра­бочих мест (АРМ) в землеустройстве. На третьем этапе, который начался в 90-е годы, произошло почти полное техническое перевооружение землеустроитель­ной службы страны, ее оснащение современной отечественной и зарубежной вычислительной техникой, что позволило поста­вить экономико-математические исследования в землеустрой­стве на качественно новый уровень. Это было связано сразу с несколькими причинами. Во-первых, появилась возможность получать цифровые мо­дели рельефа местности на основании обработки космических и аэрофотоснимков, а также топографо-геодезических данных, полученных наземным путем с использованием электронных измерительных приборов. Кроме того, стали широко использо­ваться разнообразные средства преобразования графической информации в цифровую (дигитайзеры, сканеры и др.). Во-вторых, в это время получили быстрое развитие геогра­фические информационные системы (ГИС), а в землеустрой­стве — геоинформационные или земельно-информационные системы (ЗИС). В-третьих, произошло существенное обновление электро­нно-вычислительной техники с внедрением в землеустроитель­ное производство специальных графических станций, компью­терных сетей с серверами большой мощности, средств цифровой картографии и фотограмметрии, систем автоматизи­рованного земельного кадастра и т.д. На этой базе возникли но­вые ЗИС-технологии, которые стали применять для решения конкретных землеустроительных задач и к которым начали привязывать системы автоматизированного землеустроитель­ного проектирования

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

Билет 9 Общая задача линейного программирования.

 

1. В линейном программировании все функциональные связи в системе ограничений и функции цели – линейные функции.

2. Признаки оптимальности при решении задач линейного программирования методом потенциалов. Проверяем план на оптимальность методом потенциалов, при котором каждой i-той строке устанавливается потенциал Ui, которую можно интерпретировать как цену продуктов в пункте поставщика, а каждому столбцу Vj, которую можно интерпретировать как цену продуктов у потребителя в простейших случаях цена продукции в пункте потребителя равна цене продукта поставщика + транспортные расходы:  Vj= Ui+Cij. Затем определяем оптимальность распределения через их оценки: dij = (Ui+Cij)-Vj,  получаем цену поставщика и транспортные расходы путем вычитания, сравниваем с ценой продукта у потребителя. Если оценка некоторой свободной клетки отрицательная, это можно интерпретировать так: цена, предлагаемая соответственно потребителем больше суммы цены поставщика и стоимости перевозок. Следовательно, условием оптимального распределения служит условиенеотрицательности оценок свободных клеток матрицы перевозок. Если задача стремится к максимуму, условием оптимальности является условие неположительности оценок. Проверяем план на вырожденность: количество занятых клеток равно m+n-1, а сумма строк и столбцов m+n,  если эти цифры одинаковые, план не вырожденный. Некоторому потенциалу подается произвольное значение. Цена продукта у поставщика – Ui.

 

 

Билет 10 Математическое программирование и его разделы.

 

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

 

 

Билет 11 Основные методы ЛП, применяемые для решения экономико-математических задач, их краткая характеристика.

 

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

 

Билет 12 Понятие плана. Допустимый, базисный и оптимальный план.

 

 Решение (план) – это набор значений неизвестных. Допустимое решение (допустимый план)- это набор значений неизвестных, удовлетворяющих ограничениям. Все допустимые решения образуют область определения задач линейного программирования (область допустимых решений). Базисное решение- это набор значений неизвестных, соответствующих угловых точек многоугольника (многогранника). Оптимальное решение- набор переменных, удовлетворяющих ограничению и максимизирующих или минимизирующих целевую функцию.

 

Билет 13 Теорема и крайней точке. Теорема критерия оптимальности

 

Графический метод основывается на 2х теоремах. 1. обл.определения задач лин-го программ-я представляет собой выпуклое множество и 2. целевая функция задачи лин-го программ-я достигает своего экстремального значения в угловой  точке многоугольника решения.

Билет 14 Графический метод решения простейших задач ЛП

 

Графическим методом можно решать задачи линейного программ-я, имеющих не более 2х переменных на плоскости и не более 3х переменных в пространстве. Последовательность решения задачи: 1. построили обл. допустимых решений задач. 1.1 отобразили в прямоугольной системе координат условия не отрицательности прямой. Примечание. В двухмерном пространстве уравнению соответствует пространство, а неравенстве- полуплоскость, лежащая по одну сторону от прямой. 1.2. по порядку строим прямые, соответствующие неравенству. 1.3. определяем с какой стороны от этих прямых лежат плоскости, которые удовлетворяют соответственно неравенствам системы. Берем координаты любой точки, лежащей в первой полуплоскости (например О с координатами (0;0), подставляем в неравенство ее координаты, если неравенство выполняется, то штрихуем ту полуплоскость, в которой лежит данная точка. Если не выполняется, то штрихуем противоположную полуплоскость. 1.4. определяем обл.допустимых решений, она будет представлять собой пересечение всех штрихов. 2. построим целевую функцию. 2.1. строим вектор grad (С₁, С₂)= векторN (dС₁Х₁/dХ₁; dС₂Х₂/dХ₂). Начало вектора совпадает с началом координат. 2.2 строим линию уравнения О, вектор z₀ перпендикулярен вектору N.Z₀проходит через начало координат, передвигаем Z₀ параллельно самому себе вдоль вектора N. При решении задач на min– в противоположную сторону.2.3. определяем оптимальное решение задач. Самая крайняя точка ОДР – это точка оптимума, находим ее координаты и подставляем их значения в целевую функцию. Графический метод основывается на 2х теоремах. 1. обл.определения задач лин-го программ-я представляет собой выпуклое множество и 2. целевая функция задачи лин-го программ-я достигает своего экстремального значения в угловой  точке многоугольника решения. Возможные исходы при решении ЗЛП. 1. система ограничений совместна и определяющая ею область представляет собой замкнутый выпуклый многоугольник. В этой задаче может быть одно или множество решений. 2. системы ограничений противоречивы или несовместны, т.е. не существует значение переменных, удовлетворяющих всем условиям задачи. В этом случае задачи не имеют ни допустимого ни базисного решения. 3. система ограничений совместна, но область определений ими не ограничена. Задача может в этом случае иметь множество решений или не иметь решений.

Билет 15 Основная идея симплекс метода.

 

 Для решения ЗЛП предложено немало различных алгоритмов. Наиболее эффективный симплексный метод. Симплексный метод – итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движения по угловым точкам области возможных решений до тех пор, пока не достигнет оптимального значения. В частности по угловым точкам многоугольника решений полученного геометрическим методом. Пусть решение существует, причем оптимальное значение конечно, тогда существует следующие последующие решения симплекс-м методом: 1. выбираем n- переменных, задающих допустимое пробное решение. 2. проверим, нельзя ли за счет одной переменной приравниваем в начале 0, улучшив значение целевой функции, придавая ей неотрицательное значение. Если это возможно, перейдем к 3 этапу. В противном случае прекратим вычисление. 3. найдем предельное значение переменной за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из nпеременных, вошедших в пробное решение не обратится в нуль. 

 

Билет 16 В чем состоит смысл и значение основных, дополнительных и вспомогательных переменных в экономико-математическом моделировании?