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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


контрольная работа Экономмико-математические методы и модели

Информация:

Тип работы: контрольная работа. Добавлен: 05.06.2012. Сдан: 2011. Страниц: 15. Уникальность по antiplagiat.ru: < 30%

Описание (план):


 
 
Московский  киновидеоинститут
(филиал) С.-Петербургского Государственного
университета  кино и телевидения. 
 
 
 
 
 
 
 
 
 
 
 
 

КОНТРОЛЬНАЯ РАБОТА
по дисциплине «Экономико-математические
методы  и модели» 

Вариант №5. 
 
 
 
 
 
 
 
 
 
 

                    Выполнила студентка
                    3-ого  курса факультета
                    Экономика и управление
                    Кислякова М.А.
                    Проверил: Мацнев  А. П. 
                     
                     
                     
                     
                     
                     
                     
                     
                     
                     
                     

Москва
2008 
 
 

 


Содержание
1.1. Основные понятия моделирования. Виды моделей……………………………….3
1.2.Основные методы моделирования…………………………………………………..6
1.3.Классификация видов моделирования………………………………………………6
2.1.Задача распределения  ресурсов……………………………………………………...8
2.2.Графическое решение задачи распределения ресурсов……………………………10
2.3.Симплексный метод………………………………………………………………….14
2.4.Основные способы решения транспортной задачи………………………………...18
2.5.Проверка оптимальности полученных планов перевозок методом потенциалов..20
3.1. Методы нлиннейного  программирования………………………………………….26
Список литературы……………………………………………………………………….29 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.1.Основные понятия моделирования. Виды моделей.
      Нас окружает огромное множество природных  и искусственно созданных объектов,  которое воздействует на органы чувств и отображается сознанием человека. От того, насколько верно мы воспринимаем окружающую  действительность, очень часто зависит не только наше благополучие и здоровье, но и сама жизнь. Тривиальным примером здесь может служить восприятие и оценка  пешеходом дорожной обстановки при переходе улицы.
      Не  менее сложные задачи стоят перед  человеком в процессе его профессиональной деятельности. Хотя число объектов в данном случае, как правило, становится достаточно ограниченным, но одновременно повышаются требования к уровню достоверности и точности получаемых результатов, возрастает ответственность при принятии решений. Здесь уже трудно полагаться только на органы чувств и поэтому на практике применяется целый арсенал технических  средств измерения сигналов, обработки, хранения и представления информации.
      Каждый  человек в своей повседневной жизни выделяет из бесконечного  многообразия проявлений окружающего мира только небольшое их число и на этой основе формирует некоторые заменители реальных объектов, позволяющие ему выстраивать целенаправленное поведение. Эти заменители принято называть моделями.
      Таким образом, условимся под моделью  понимать заменитель реального объекта в тех свойствах и отношениях, которые требуются для решения практических задач. Соответственно моделирование будем рассматривать как метод опосредованного познания, в котором объект-модель находится в некотором неполном соответствии с объектом-оригиналом.
      Принято говорить, что модель адекватна оригиналу, если она верно отражает интересующие нас свойства оригинала. В данном случае важно уяснить принципиальную разницу понятий адекватности и идентичности (полного совпадения) объекта и модели. Последнее понятие, строго говоря, характеризует отношение объекта к самому себе.
      Второе  обстоятельство, которое в определенной мере облегчает наше существование  в бесконечно разнообразном мире, основывается на его материальном единстве, проявляющемся в подобии (аналогии) разноплановых явлений и процессов. При этом под аналогией принято понимать суждение о сходстве нескольких объектов в определенных отношениях на основании установленного сходства их в других отношениях.
      Понятно, что соотношение оригинала и модели также определяется свойством аналогии, т.е. сходством нетождественных объектов в некоторых качествах и отношениях. На основании аналогии строится теория подобия, позволяющая по установленным свойствам одного объекта судить о больших группах объектов, подобных первому объекту.
      Интересно также отметить взаимосвязь моделирования  с информацией, понимаемой как содержание воздействий, значения их параметров, изменения этих параметров в пространстве и во времени, взятые в отрыве от физического носителя информации и от его энергетических свойств.
      Овладение информацией, ее преобразование, хранение и отображение невозможны без  моделирования, т.е. без отображения  в некоторой материальной среде (в человеческом мозге, на запоминающих устройствах ЭВМ, на экране дисплея или на листе бумаги).
      Принято различать следующие виды моделей: 
      §          мыслительные;
      §          словесные (вербальные);
      §          геометрические;
      §          физические;
      §          математические.
      Мыслительные модели формируются и хранятся в сознании человека в виде некоторых образов. Словесные модели можно рассматривать как отражение мыслительных моделей, предназначенное для обмена информацией между людьми. Описание формулы изобретения, текст программы для ЭВМ, инструкция по эксплуатации некоторого технического устройства, литературное произведение – все это примеры словесных моделей.
      Геометрические модели дают внешнее представление об объекте-оригинале и характеризуются одинаковыми с ним пропорциями геометрических размеров. Эти модели подразделяются на двумерные и трехмерные. Эскизы, схемы, чертежи, графики, живописные работы представляют собой примеры двумерных геометрических моделей, а макеты зданий, автомобилей, самолетов и т.д. – это трехмерные геометрические модели.
      Физические модели характеризуются тем, что имеют ту же физическую природу, что и объект-оригинал. Например, система энергоснабжения города может быть смоделирована на специальной электрической схеме, аэродинамика летательного аппарата исследуется при продуве его модели в аэродинамической трубе и пр.
      Наконец, математические модели представляют собой совокупность математических объектов (чисел, символов, множеств и т.д.) и связей между ними, отражающих необходимые свойства объекта-оригинала. При этом математические модели принято подразделять на модели-аналоги, структурные модели и алгоритмические модели.
      Построение  моделей-аналогов основывается на свойстве  изоморфизма (одинаковости) математического описания процессов различной физической природы. Например, взаимосвязи приложенной силы, массы тела и его ускорения для механической системы, напряжения, индуктивности и скорости изменения тока во времени для электрической цепи, теплового потока, теплоемкости и скорости изменения температуры во времени для тепловой системы описываются одинаковыми математическими соотношениями. Используя свойство изоморфизма, можно с помощью одних объектов (чаще всего электрических цепей) исследовать процессы в объектах другой физической природы (тепловых, механических, гидравлических и др.).
      С помощью структурной математической модели воспроизводится структура уравнений, описывающих поведение исследуемого объекта.
      Например, уравнение, позволяющее получить зависимость  скорости падения v тела массой m в среде с коэффициентом вязкости k
(1.1.)

может быть разрешено относительно производной  скорости
(1.1.2.)

и представлено в виде схемы, включающей интегрирующее, суммирующее и множительное устройства (рис1.1):
      

Рис. 1.1. Схема с интегрирующим, суммирующим 
и множительным устройством
      На  принципах структурного математического моделирования работают аналоговые вычислительные машины.
      Алгоритмические модели воспроизводят пошаговый процесс численного решения уравнений, представляющих математическую модель исследуемого объекта. Если алгоритмические модели реализуются на цифровых вычислительных машинах (компьютерах), то они могут рассматриваться как структурные модели, работающие с цифровой информацией. В данном случае все преобразования информации выполняются одним и тем же структурным элементом – процессором. Последовательность решения задается программой, а алгоритмические модели часто называют цифровыми. Следует отметить, что применение компьютеров делает алгоритмические модели наиболее универсальными: например, с их помощью могут быть воспроизведены и модели-аналоги, и структурные математические модели.  
      Кроме того, алгоритмический подход к математическому  моделированию и применение компьютеров  позволяют выполнять и геометрическое моделирование. Об успехах этого  вида моделирования имеет представление каждый любитель мультипликационных фильмов и телевизионных клипов: большинство из них сделано с применением средств компьютерного геометрического моделирования.
1.2.Основные методы моделирования.
     Развитие  методы моделирования получили с  развитием вычислительной техники. Исторически первыми были разработаны аналитические методы моделирования и сложился аналитический подход к исследованию систем.
     Аналитические методы моделирования. Аналитические методы позволяют получить характеристики системы как некоторые функции параметров ее функционирования. Таким образом, аналитическая модель представляет собой систему уравнений, при решении которой получают параметры, необходимые для оценки системы (время ответа, пропускную способность и т.д.). Использование аналитических методов дает достаточно точную оценку, которая, зачастую, хорошо соответствует действительности. Смена состояний реальной системы происходит под воздействием множества как внешних, так и внутренних факторов, подавляющее большинство из которых носят стохастический характер. Вследствие этого, а также большой сложности большинства реальных систем, основным недостатком аналитических методов является то, что при выводе формул, на которых они основываются и которые используются для расчета интересующих параметров, необходимо принять определенные допущения. Тем не менее, нередко оказывается, что эти допущения вполне оправданы.
     Численные методы моделирования  – преобразование модели к уравнениям, решение которых возможно методами вычислительной математики. Класс задач значительно шире. Однако численные методы не дают точных решений, но позволяют задать точность решения.      
     Имитационные  методы моделирования. С развитием вычислительной техники широкое применение получили имитационные методы моделирования для анализа систем, преобладающими в которых являются стохастические воздействия.
Суть ИМ заключается  в имитации процесса функционирования системы во времени, соблюдением  таких же соотношений длительности операций как в системе оригинале. При этом имитируются элементарные явления, составляющие процесс; сохраняется их логическая структура, последовательность протекания во времени. Результатом ИМ является получение оценок характеристик системы.
1.3.Классификация видов моделирования.
В основу классификации  моделирования можно положить различные признаки.
     В зависимости от характера изучаемых процессов в системе все виды моделирования м.б. разделены на
     - детерминированные и стохастические  
      Детерминированное моделирование применяется для  исследования систем, поведение которых можно абсолютно точно предвидеть. Например, путь, пройденный автомобилем, при равноускоренном движении в идеальных условиях; устройство, возводящее в квадрат число на входе. Соответственно детерминированный процесс, детерминированная модель.
      Стохастическое (теоретико-вероятностное) моделирование  применяется для исследования систем, состояние которых зависит не только от контролируемых, но и от неконтролируемых воздействий или в ней самой  есть источник случайности. Например, человек и все системы, которые включают человека. Приведем пример стохастических систем, это - заводы, аэропорты, сети и системы ЭВМ, магазины, предприятия бытового обслуживания и т.п.
     - статическое и  динамическое 
     Статистическое  моделирование служит для описания систем в какой-либо момент времени.
     Динамические  моделирование отражает изменение  системы во времени (выходные характеристики системы в данный момент времени  определяются характером входных воздействий  в прошлом и настоящем). Устройство, возводящее x(t) в квадрат. Примером динамических систем является биологические, экономические, социальные системы; такие искусственные системы как завод, предприятия, поточная линия и т.п.
     - дискретное и непрерывное 
     Дискретное  моделирование применяют для  исследования систем, в которых входных и выходные характеристики измеряется или изменяется во времени дискретно, через dt (например, часы), в противном случае применяют непрерывное моделирование. Например: ЭВМ, электронные часы, электросчетчик - дискретные системы; песочные часы, солнечные часы, нагревательные приборы и т.д. - непрерывные системы.
     В зависимости от формы представления  объекта (системы) можно выделить мысленное  и реальное моделирование.
     При реальном (натурном) моделировании  исследование характеристик системы  проводится на реальном объекте, либо на его части. РМ является наиболее адекватным, но его возможности с учетом особенностей реальных объектов ограничены. Например, проведение реального моделирования с АСУ предприятия требует во-первых, создания АСУ; во-вторых, проведения экспериментов с предприятиями, что невозможно.
     К реальному моделированию относят  производственный эксперимент и  комплексные испытания, которые  обладают высокой степенью достоверности.
     Другой  вид реального моделирования  – физическое. При физическом моделировании исследование проводится на установках, которые сохраняют природу явления и обладают физическим подобием.
     Мысленное моделирование применяется для  моделирования систем, которые практически  не реализуемы на заданном интервале  времени. В основе мысленного моделирования - создание идеальной модели основанной на идеальной, мыслительной аналогии. Различают два вида моделирования: образное (наглядное) и знаковое.
     При образном моделировании на базе представлений  человека о реальных объектах создаются различные наглядные модели, отображающие явления и процессы, протекающие в объекте (например, модели частиц газов в кинетической теории газов в виде упругих шаров, воздействующих друг на друга во время столкновения).
     При знаковом моделировании описывают  моделируемую систему с помощью условных знаков, символов, в частности, в виде математических, физических и химических формул.
     Наиболее  мощный и развитый класс знаковых моделей представляют математические модели.
     Математическая  модель – это искусственно созданный объект в виде математических, знаковых формул, который отображает и воспроизводит структуру, свойства, взаимосвязи и отношения между элементами исследуемого объекта. Именно этот класс моделей мы и будем рассматривать и далее говорить только о математическом моделировании.
     Математическое  моделирование (Губарев В.В.) – метод исследования, основанный на замене исследуемого объекта-оригинала его математической моделью и на работе с ней (вместо объекта).
     Математическое  моделирование можно разделить  на аналитическое, имитационное, комбинированное.
     При АМ создается аналитическая модель объекта в виде алгебраических, дифференциальных, конечно-разностных уравнений. Аналитическая  модель исследуется либо аналитическими методами, либо численными методами.
     При имитационном моделировании создается Имитационная модель, используется метод статистического моделирования для реализации Имитационной модели на ЭВМ.
     Комбинированное моделирование – декомпозиция процесса функционирования системы на подпроцессы. Для тех из них, где это возможно, используют аналитические методы, в противном случае – имитационные.   
2.1.Задача  распределения ресурсов.
     Линейное  программирование - представляет собой математический аппарат, разработанный для решения оптимальных задач с линейными выражениями для критерия оптимальности и линейными ограничениями на область изменения переменных. Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и прочего.
     Задачами  линейного программирования называются задачи, в которых линейны как  целевая функция, так и ограничения  в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.
     Линейное  программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи: рационального использования сырья и материалов; задачи оптимизации раскроя; 
оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; составления оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования.

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

     X1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств:
     A1X1 + A1X2 + … + A1Xn = B1;
     A2X1 + A2X2 + … + A2Xn = B2;
     AmX1 + AmX2 + … + AmXn = Bm;
     Xj 0, j=1,…,n и обращающих в максимум линейную функцию этих переменных: 
F = C1X1 + C2X2 + … + CnXn (max)

     При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия:
     Bj 0, j=1,…,n
     Приведение к стандартной форме необходимо, так как большинство методов решения задач линейного программирования разработано именно для стандартной формы. Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия:
     - перейти от минимизации целевой  функции к ее максимизации;
     - изменить знаки правых частей  ограничений;
     - перейти от ограничений-неравенств  к равенствам;
     - избавиться от переменных, не  имеющих ограничений на знак.
     
Характеристика Вид продукции Располагаемый ресурс
П1 П2
Резервы: трудовые
 
1
 
3
 
14
материальные 3 4 25
финансовые 7 2 43
Выпуск 1 1 -
Прибыль 6 8 -
План х1 х2 -
Целевая функция а) х1 + х2         max б) прибыль         max
       Далее рассмотрим на конкретных  примерах различные методы решения задач линейного программирования.
2.2.Графическое решение задачи распределения ресурсов
     Пусть для двух продуктов П1 и  П2 требуются трудовые, материальные и финансовые ресурсы. Наличие ресурсов каждого вида и их нора расхода, необходимые     

                 Таблица 1.
     для выпуска единицы продукции, приведены  в таблице 1.
     По  условию данной задачи нам надо найти  значение переменных, при которых:                а) суммарный выпуск будет максимальным; б) Максимальная прибыль. 

                                                                                                                                        

     Для начала составим математическую модель задачи:                                                                                                                                        
         х1 + 3х2 14
          3х1 + 4х 25
          7х1 + 2х2 43
     х1 0, х2
     Математическая  модель представляет собой систему  линейных неравенств. Значит, область допустимых значений нашей задачи выпуклый многоугольник. Для удобства построения неравенства можно записать в форме, аналогичной уравнениям в отрезках:
      х1/14 + х2 /14/3
     х1/25/3 + х2 /25/4 1
     х1/43/ 7 + х2/43/2 1
     х1 0, х2 0
      х1/14 + х2/4,666
     х1/8,33 + х2/6,25  1
     х1/6,143 + х2/21,5 1
     х1 0, х2 0
а) Если мы хотим найти оптимальное решение, то должны принять целевую функцию. Рассмотрим сначала первый вопрос - максимализацию суммарного выпуска:
     Тогда целевая функция:
      F1 = х1 + х2       max
       Эту зависимость представим в виде х2 = f - х1. Из графика данного уравнения (рис.1.) следует, что tg = -1, при этом = 1350, а величина F равна отрезку, отсекаемому прямой функции цели на оси координат. Если эту величину перемещать параллельно самой себе в направлении, указанном стрелками, то эта величина будет возрастать. Очевидно , что оптимальным решением будут координаты  точки   С = (х1, х2).
      На  основании рассмотренного, можно  сделать исключительно важный вывод: оптимальным решением являются координаты вершин ОДР. На этом базируется аналитический метод решения задач линейного программирования, который заключается в следующем:
    Найти вершины ОРД, как точки пересечения ограничений.
    Определить последовательно значения целевой функции в вершинах.
    Вершина, в которой ЦФ приобретает оптимальное (максимальное или минимальное) значение, является оптимальной вершиной.
    Координаты этой вершины и являются искомыми оптимальными значениями переменных.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
     Рис. 2.2. 

     Если  направление целевой функции  совпадает с направлением одной  из сторон, то у задачи будет, по крайней мере, два решения. В таком случае говорят, что задача имеет альтернативные решения. А это значит, что одно и то же оптимальное значение целевой функции может быть получено при различных значениях переменных.
     Тот факт, что оптимальное решение  находится на вершине ОДР, дает ещё 2 очень важных вывода:
     - Если оптимальным решением являются  координаты вершин ОДР, значит, сколько вершин имеет ОДР, столько  оптимальных решений может иметь  задача.
     - Поскольку чем больше ограничений,  тем больше вершин, то следовательно, чем больше ограничений, тем больше оптимальных решений.
     Как видно на рис.2.2., вершина, координаты которой являются оптимальным решением, определяется углом наклона прямой описывающей целевую функцию. Значит, каждая вершина будет соответствовать оптимальному решению для некоторой целевой функции.  Исходя из этого, найдем оптимальное решение для второй функции:
      б)  F2 = 6х1 + 8х2       max (максимизация прибыли)
          6х1 = f – 8х2 .         
     Из  графика уравнений следует, что tg = - , а величина f равна отрезку, отсекаемому прямой функцией цели на оси координат (рис.2.2.).
     Так же мы можем найти следующие функции:
      F3 = х1           max  (максимализация выпуска продукции П1)
      F4 = х2       max (максимализация выпуска продукции П2)    
      F5 = (1+3+7) х1 + (3+4+2) х2 = 11х1 + 9х2         max (минимизация используемых ресурсов). 
     Для каждой целевой функции, так же как  и для F1, можно построить линию целевой функции и определить вершину, в которой целевая функция будет иметь оптимальное значение. Результаты решения задачи по пяти целевым функциям сведем в таблицу 2.
                                                                                                                                   Таблица 2.
Целевая функция Вершина х1 х2 х1 +  х2 Прибыль Используемый  ресурс
F1 = х1 + х2 max В 5,5 2 7,5 49 78,5
F2 = 6х1 + 8х2 max В 3,5 3,5 7 49 70
F3 = х max  А 6,14 0 6,14 36,84 67,54
F4 = х2 max С 0 4,66 4,66 37,28 41,94
F5=11х1+9х2 0 0 0 0 0 0
 
 
2.3.Симплексный  метод
Для аналитического решения задач линейного программирования разработан специальный алгоритм направленного  перебора вершин ОРД (области допустимых решений). Этот алгоритм обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается. В геометрии есть такое понятие, как "симплекс". Симплексом тел в К-мерном пространстве называется совокупность (К+1) его вершин. Так, для плоскости при К=2 симплексом будут 3 вершины треугольника. При К=3 - 4 вершины четырехгранника и т.д. С учетом этого понятия аналитический метод решения задач линейного программирования называется симплекс-метод. Он основан на алгоритме направленного перебора вершин. Вычисления, обеспечивающие определение значения целевой функции и переменных в одной вершине называются итерацией.
     В настоящее время этот метод является одним из основных методов решения  задач линейного программирования. Более подробно симплексный метод  решения задач мы рассмотрим на примере этой же задачи.
      х1 + 3х2 14
     1 + 4х 25
     1 + 2х2 43
а) Функция цели f = 6х1 + 8х2       max
х1 0, х2 0
     Симплексный метод предназначен для решения  задач в канонической форме. Что бы перевести наше неравенство в каноническую форму введем новые неотрицательные  переменные y1, y2, y3 и перейдем от системы неравенств к системе уравнений.
       х1 + 3х2 + 1y1 + 0y2 + 0y3 14 
     1 + 4х+ 0y1 + 1y2 + 0y3 25
     1 + 2х+ 0y1 + 0y2 + 1y3 43
     f = 6х1 + 8х2 + 0y1 + 0y2 + 0y3
     Для удобства составления симплекс таблицы  перепишем данную систему в виде              0-уравнения:
              0 = 14 - (х1 + 3х+ 1y1 + 0y2 + 0y3)
             0 = 25 - (3х1 + 4х + 0y1 + 1y2 + 0y3)         
             0 = 43 - (7х1 + 2х + 0y1 + 0y2 + 1y3)                       
             0 = f –(1 + 8х2 + 0y1 + 0y2 + 0y3)
     Данную  систему можно записать в виде одного векторного равенства:
        0 = В – (А1х1 + А2х2 + А3у1 + А4у2 + А5у3),
где, вектор-столбец  В имеет своими компонентами свободные члены, а вектор А1, А2, …. А5 – коэффициенты при соответствующих переменных х1, х2 , у1 , у2 , у3. Иными словами:
                  14             1              3              1              0             0                                                        
           В=  25  , А1=   3  , А2 =  4   , А3 =  0  ,  А4=  1  ,  А5=  0  .                                                                                          
           43              7             2              0              1             1                                                       
     Линейная  форма имеет вид:
     f = 6х1 + 8х2 + 0y1 + 0y2 + 0y3.
     Векторы А3,  А4,  А5 образуют базис. Это означает, что, присвоив х1 = 0, х2 = 0, получаем первое базисное решение: х1=0; х2=0; у1=14; у2=25; у3 =43.
     При этом линейной формы f = 0. На этом основании строим первую симплексную таблицу 3.
     
№ Ите - рации
Базисные  векторы Вектор  свободных членов В Векторы min симплпексные отношения
А1 А2 А3 А4 А5
 
1.
А3 14 1 3 1 0 0 14/3=4,666
А4 25 3 4 0 1 0 25/4=6,25
А5 43 7 2 0 0 1 43/2=21,5
Индексная строка Fi - Cj 0 -6 -8 0 0 0  
                                                                                                                                            Таблица 3.
     Так как мы решаем задачу на максимализацию прибыли, то из выражения линейной формы  видно, что имеет смысл увеличить х1 или х2 (так как коэффициенты при этих переменных отрицательны в скобках).  Если мы предположим что х1 0 или х2 0, то значение f увеличится. Эти же коэффициенты с их знаками стоят в индексной строке. Из этого следует, что наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что оптимальное решение ещё не получено, и то, что от таблицы    надо перейти к следующей.
     Переход к новой таблице, то есть к новой  улучшенной программе, осуществляется по следующему алгоритму:
    В индексной строке находим наибольшее по абсолютному значению отрицательное число. В нашем примере это будет – 8. Найденной число определяет ведущий или ключевой столбец.
    Делим свободные члены на положительные элементы ведущего столбца и из полученных отношений выбираем наименьшее, это отношение и определит ведущую строку. В данной таблице мы проделали эту процедуру в последнем столбце, и из полученных результатов видно, что ведущей строкой является вторая строка А4.
    На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент. В данной задаче – это число 5.
    Теперь преступаем к составлению второй таблицы:
    а) Вместо единичного вектора А4 мы в базис вводим  вектор А2.
    б) Переход  к новому базису, как это известно, эквивалентен элементарному преобразовании матрицы, элементами которой служат числа таблицы 4. А именно: в новой таблице элемент строки, соответствующий элементу ведущей строки прежне таблицы, равен этому элементу ведущей строки, разделенному на разрешающий элемент.
    в) Что  бы получить любой другой элемент  новой симплексной таблицы нужно  от соответствующего элемента прежней  таблицы отнять произведение элемента ведущей строки на элемент ведущего столбца, разделено на разрешающий  элемент.
                                                                                                                                 Таблица 4.   
№ Ите - рации
Базисные  векторы Вектор  свободных членов В Векторы min симплпексные отношения
А1 А2 А3 А4 А5
 
2.
А2 4,666 0,33 1 0,33 0 0 4,66/0,33=14,12
А4 6,333 1,66 0 -1,33 1 0 6,33/1,66=3,81
А5 33,666 6,33 0 -0,66 0 1 33,66/6,33=5,31
Индексная строка Fi - Cj 37,333 -3,33 0 2,66 0 0  
 
Из  таблицы 4   видно, что значение линейной формы возросло и теперь равно 6. Однако наличие в индексной строке отрицательных чисел свидетельствует о том, что это значение еще модно увеличить. Переходим к следующей симплексной таблице. Число «0,4» определяет ведущий столбец. А, как видно из последнего столбца минимальных симплексных отношений, число 6 определяет ведущую строку. Итак, разрешающим элементом  будет 2,2. Вектор А1 вводим в базис вместо вектора А3. пересчет коэффициентов осуществляем по указанным выше правилам и получаем таблицу.
                                                                                                                                  Таблица  5.       
№ Ите - рации
Базисные  векторы Вектор  свободных членов В Векторы
А1 А2 А3 А4 А5
 
3.
А2 3,4 0 1 0,45 0,27 0
А1 3,8 1 0 -0,27 0,03 0
А5 9,5 0 0 -0,36 -1,61 1
Индексная строка Fi - Cj 30 0 0 0,18 1,3 0
 
     В индексной строке нет отрицательны элементов. Следовательно, мы получили оптимальную программу. Оптимальное  решение:
     х1= 3.8,  х2= 3,4,  у1= 9,5,  у2=0,  у3 =0.
б) Теперь с помощью симплексных  таблиц найдем решение целевой функции на оптимизацию суммарного выпуска:   f = х1 + х2       max
     х1 0, х2 0
     Линейная  форма имеет вид:
     f = 1х1 + 1х2 + 0y1 + 0y2 + 0y3.
     Векторы А3,  А4,  А5 образуют базис. Это означает, что, присвоив х1 = 0, х2 = 0, получаем первое базисное решение: х1=0; х2=0; у1=27; у2=2; у3 =42.
     При этом линейной формы f = 0. На этом основании строим первую симплексную таблицу.
                                                                                                                                   Таблица  6.                    
№ Ите - рации
Базисные  векторы Вектор  свободных членов В Векторы min симплпексные отношения
А1 А2 А3 А4 А5
 
1.
А3 27 4 3 1 0 0 27/4 = 6,75
А4 23 3 5 0 1 0 23/3 = 7,66
А5 42 5 7 0 0 1 42/5 = 8,4
Индексная строка Fi - Cj 0 -1 -1 0 0 0  
 
     Так как в индексной строке присутствуют отрицательные числа, то используя  вышеописанный алгоритм, переходим  к следующей симплексной таблице. Ведущий столбец будет  А1, минимальное симплексное отношение определяет ведущую строку и в данном случае ведущая строка будет первой.  Разрешающий элемент будет 4.                                                                                                                                           
                                                                                                                          Таблица 7.       
№ Ите - рации
Базисные  векторы Вектор  свободных членов В Векторы min симплпексные отношения
А1 А2 А3 А4 А5
 
2.
А1 6,75 1 0,75 1,25 0 0 6,75/0,7 = 9,64
А4 2,75 0 2,75 -0,75 1 0 2,75/2,75 = 1
А5 8,25 0 3,25 -1,25 0 1 8,25/3,25 =2,53
Индексная строка Fi - Cj 6,75 0 -0,25 0,25 0 0  
 
     В  таблице 7 тоже есть отрицательные числа в индексной строке, это означает, что мы ещё не получили оптимальное решение в данной таблице. Поэтому переходим  к следующей симплекс таблице.                                                                                                                               
                                                                                                                   Таблица 8.    
№ Ите - рации
Базисные  векторы Вектор  свободных членов В Векторы
А1 А2 А3 А4 А5
 
3.
А1 6 1 0 1,45 -0,27 0
А2 1 0 1 -0,45 0,36 0
А5 5 0 0 -2,13 -1,18 1
Индексная строка Fi - Cj 7 0 0 0,18 0,09 0
 
     В индексной строке нет отрицательны элементов. Следовательно, мы получили оптимальную программу. Оптимальное  решение:
     х1= 6,  х2= 1,  у1= 7,  у2=0,  у3 =0.
2.4. Основные способы решения транспортной задачи
Задачи  транспортного типа широко распространены в практике. Кроме того, к ним  сводятся многие другие задачи линейного  программирования - задачи о назначениях, сетевые, календарного планирования. Рассмотрим  типовое решение транспортной задачи на конкретном примере.
     В 4 пунктах отправления  А1, А2 , А3, А4 (поставщики) сосредоточено определенное количество единиц некоторого продукта, которое обозначим аi (i=1,2,3,4). Данный продукт потребляется в 5 пунктах В1, В2, В3, В4, В5 (потребители); объем потребления обозначим bj (j=1, 2, 3, 4, 5). Будем считать, что общее количество продукции у всех поставщиков равно суммарной потребности в ней. Известны расходы на перевозку единицы продукта из пункта Аi в пункт Вj, которые равны сij и приведены в матрице транспортных расходов С= (сij).
     Задача  состоит в определении такого плана перевозок, при котором  весь продукт вывозится из пунктов  Аi в пункты  Вj в соответствии с потребностью и общая величина транспортных издержек будет минимальной. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью.
     Стоимости  Сij перевозки единицы продукции заданы в виде таблицы 9.
     Решение:
     1) Для первоначального (опорного) закрепления потребителей за поставщиками воспользуемся методом северо-западного угла.
     Число занятых клеток m + n – 1 = 4  + 5 = 8. 

                                                                                                                                              Таблица 9.     
ПН ПО
В1 В2 В3 В4 В5 Аi
А1 9 7 15 8 7 30
А2 12 8 10 8 15 40
А3 6 10 10 12 14 35
А4 16 10 8
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


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