Контрольная работа по «Экономико-математическое моделирование»

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ИЖЕВСКАЯ ГОСУДАРСТВЕННАЯ СЕЛЬСКОХОЗЯЙСТВЕННАЯ АКАДЕМИЯ» 

КАФЕДРА ИНФОРМАТИКИ 

                                         

                                                  

КОНТРОЛЬНАЯ РАБОТА

по  дисциплине: «Экономико-математическое моделирование»

Вариант№8 
 

    Выполнила:

студентка 4 курса  БУА и А              А.В. Иванова

заочного отделения

шифр 06038   

   Проверил:

                                                                                      Н.В. Горбушина

       
 
 
 

     Ижевск 2009  

Содержание: 
 
 

1. Вопрос  №1…………………………………………………………………3
2. Вопрос №2……………………………..…………………………………..8
3. Задача №1………………….………………………………………………16
4. Задача №2………………………………………………………………….17
5. Список литературы……………………….………………………………19

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Вопрос  №1. Признак оптимальности при  решении транспортной задачи методом  потенциалов.

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

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

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

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

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

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

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

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

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

     Одно  из неизвестных последовательности свободное, а все остальные - базисные.

     Каждые  два соседних в последовательности неизвестных лежат либо в одном  столбце, либо в одной строке.

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

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

     Второе  условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

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

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

     старые  значения;

     новые значения.

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

     Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак “+”, т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.

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

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

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

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

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

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

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

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

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

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

     В зависимости от методов подсчета алгебраических сумм тарифов для  свободных клеток различают два  метода отыскания оптимального решения транспортной задачи:

     Распределительный метод. При этом методе для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов.

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

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

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

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

     Вопрос  №2. Управление запасами.

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

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