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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


Реферат/Курсовая Линейное програннирование

Информация:

Тип работы: Реферат/Курсовая. Добавлен: 30.05.13. Сдан: 2012. Страниц: 9. Уникальность по antiplagiat.ru: < 30%

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


Федеральное агентство железнодорожного транспорта

Сибирский государственный  университет путей  сообщения 
 
 
 

Кафедра «Бухгалтерский учет и аудит на железнодорожном транспорте» 
 
 

Курсовая  работа 

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

Руководитель:                                                                           Разработал:

                                                                                                    студент ЗФ  09-ВЭ-59 

___________   Баранова  Н.В.                                              __________ Маликов Р.Ф.

      (подпись)                                                                                     (подпись)

______________                                                           _____________

  (дата проверки)                                                                   (дата сдачи на проверку) 
 
 
 

Краткая рецензия

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

_____________________

    (запись о доступе к защите)

______________________                                                         ______________________

  (оценка по результатам защиты)                                                                                           (подпись преподавателя) 
 
 

Новосибирск 2011 
 

Задача  № 1

Дана задача линейного программирования:

Требуется:

  1. Решить исходную задачу графическим способом.
  2. Построить симметричную двойственную задачу и решить ее аналитическим способом.
  3. Используя теоремы двойственности, найти оптимальные оценки исходной задачи.

Решение.

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

Построим  в системе координат Oх1х2 прямые, соответствующие неравенствам системы:

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

Целевая функция Z= достигает своих оптимальных значений в вершинах построенного многоугольника.

 
 
 
 
 

  
 
 
 
 
 
 
 
 
 

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

          

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

 

Отсюда видно, что целевая функция Z= достигает своего минимального значения -14 в точке В(2,3).

 Таким образом,  задача имеет решение  . 

2. Преобразуем систему

 в систему   

Каждому ограничению в исходной задаче должно соответствовать неизвестное в двойственной задаче:

 

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

 

Получим систему  ограничений для двойственной задачи:

 

 

Решим симметричную двойственную задачу аналитическим  способом.

Найдем  наибольшее значение линейной функции при следующих ограничениях:

Получим

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

     К левой части неравенства 1 системы  ограничений прибавляем неотрицательную  переменную y4, тем самым мы преобразуем неравенство 1 в равенство. От левой части неравенства 2 системы ограничений отнимаем неотрицательную переменную y5, тем самым мы преобразуем неравенство 2 в равенство.

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

     Определимся с начальным опорным решением.

     Переменная  y4 входит в уравнение 1 с коэффициентом 1, а в уравнение 2 системы с коэффициентом ноль, т.е. y4 - базисная переменная.

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

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

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

     Из  уравнения 2 последней системы выразим  y6 и подставим в выражение функции W:

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

     Для составления начальной симплекс таблицы выполнены все условия.

При составлении  исходной симплекс таблицы, коэффициенты при переменных функции Z*(y) записываются с противоположными знаками, а свободный член со своим знаком.

Для функции W правило такое же.

     За  ведущий выберем столбец 2, так  как -2 - наименьший элемент в строке W (если есть несколько одинаковых наименьших, то выбираем любой). Элемент строки W, принадлежащий столбцу свободных членов, не рассматриваем.

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

базисные 
переменные
y1 y2 y3 y4 y5 y6 свободные 
члены
отношение
y4 1 1 -1 1 0 0 2 2/1=2
y6 -1 2 2 0 -1 1 6 6/2=3
Z*(y) -3 -5 0 0 0 0 0  
W 1 -2 -2 0 1 0 -6  
 

     От  элементов строки 2 отнимаем соответствующие элементы строки 1, умноженные на -2. От элементов строки Z*(y) отнимаем соответствующие элементы строки 1, умноженные на -5. От элементов строки W отнимаем соответствующие элементы строки 1, умноженные на -2. Базисной является теперь переменная y2. Элементы столбца y6 можно не пересчитывать, так как переменная y6 больше не является базисной. 

базисные 
переменные
y1 y2 y3 y4 y5 свободные 
члены
отношение
y2 1 1 -1 1 0 2  
y6 -3 0 4 -2 -1 2 2/4=0.5
Z*(y) 2 0 -5 5 0 10  
W 3 0 -4 2 1 -2  
 

     За  ведущий выберем столбец 3, так как -4 - наименьший элемент в строке W.

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

базисные 
переменные
y1 y2 y3 y4 y5 свободные 
члены
отношение
y2 1 4 0 2 -1 10  
y3 -3 0 4 -2 -1 2  
Z*(y) -7 0 0 10 -5 50  
W 0 0 0 0 0 0  
 

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

базисные 
переменные
y1 y2 y3 y4 y5 свободные 
члены
отношение
y2 1 4 0 2 -1 10 10/1=10
y3 -3 0 4 -2 -1 2  
Z*(y) -7 0 0 10 -5 50  
 

     За  ведущий выберем столбец 1, так как -7 - наименьший элемент в строке Z*(y).

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

От элементов строки 2 отнимем соответствующие элементы строки 1, умноженные на -3. От элементов строки 3 отнимем соответствующие элементы строки 1, умноженные на -7.  

базисные 
переменные
y1 y2 y3 y4 y5 свободные 
члены
отношение
y1 1 4 0 2 -1 10  
y3 0 12 4 4 -4 32  
Z*(y) 0 28 0 24 -12 120  
 

     За  ведущий выберем столбец 5, так  как -12 – наименьший элемент в  строке Z*(y). В разрешающем столбце все элементы отрицательные, поэтому решение данной задачи симплекс методом бесконечно. 
 

3. Согласно первой теореме двойственности, необходимо выполнение условия Z(x)= Z*(y).

Найдем с помощью  надстройки «Поиск решения» в электронной  таблице Excel решение исходной задачи. 

 

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

 

Задача  № 2

Дана задача линейного программирования:


и т.д.................


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


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


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


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


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