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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


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

Информация:

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

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


СОДЕРЖАНИЕ 

    
    Симплексный метод в линейном программировании.                        3
    Двойственность в линейном программировании.                               8
    Транспортная задача.                                                                           9
    Сетевое планирование и управление. Расчёт основных показателей.12
    Библиографический список.                                                                    17 

 

 

    СИМПЛЕКСНЫЙ МЕТОД В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ.
 
     Дано: Для производства двух видов продукции А и В можно используется сырьё трёх видов. При этом на изготовление единицы изделия А расходуется 2 ед. сырья первого вида, 4 – ед. 2-го и 3 – ед. 3-го вида. На изготовление единицы изделия В расходуется 3 ед. сырья 1-го вида, 2 – ед. 2-го вида, 5 – ед. 3-го вида сырья. На складе фабрики имеется сырья 1-го вида 35 ед., 2-го – 42, 3-го – 49 ед. От реализации единицы готовой продукции А фабрика имеет прибыль 3 тыс. руб., а от продукции В прибыль составляет 3 тыс. руб.
     Найти: Найти решение симплексным методом и графически.
     Решение: Данные о расходе сырья на производство единицы продукции, запасов сырья и прибыли от реализации единицы продукции вносим в таблицу. 

    Вид сырья Запасы  сырья Расход  сырья на 1 ед. продукции
    А В
    1 2
    3
    35 42
    49
    2 4
    3
    3 2
    5
    Прибыль от реализации 1 ед. продукции 3 3
 
     Составим  математическую модель.
      Обозначим через х1 и х2 выпуск продукции А и В соответственно. Затраты не должны превышать запасы:
2x1 + 3x2 ? 35,
4x1 + 2x2 ? 42,
3x1 + 5x2 ? 49. 

     Прибыль от реализации х1 единиц А и х2 – В составит z = 3x1+3x2 ,
     Получили  модель задачи:
   1 + 3х2 35,
   1 + 2х2
42,

   1 + 5х2
49,

   х1
0; x2
0

              z = 3x1 + 3x2
  

  
     Вводим  балансовые переменные х3, х4, х5.
     Получим модель в каноническом виде. 

          2x1 + 3x2 + x3             = 35,
          4x1 + 2x2 +      x4        = 42,                      
          3x1 + 5x2             + x5 = 49.      
   xj
0; (j=1,...,5);

   z = 3x1 + 3x2
.
 

     Составим  симплексную таблицу: 

cj базис (xj)
аi0 3 3 0 0 0
х1 х2 х3 х4 х5
0 0
0
x3 x4
x5
35 42
49
2 4
3
3 2
5
1 0
0
0 1
0
0 0
1
 
  Z 0 -3 -3 0 0 0  
 
     Первые  три строки этой таблицы содержат в условной форме систему уравнений (ограничений) в канонической задаче. Последняя строка – оценочной, а элементы строки – оценками. Первый элемент а00 оценочной строки представляет собой значение целевой функции z на начальном опорном плане:
= (0, 0, 35, 42, 49)

а00 =

а01

а02
 

     Оценки  при всех базисных неизвестных всегда равны нулю.
     Выбираем  разрешающий столбец по наименьшей отрицательной оценке. Вычисляем : для этого делим свободные члены на положительные элементы разрешающего столбца. Выделим разрешающий элемент, соответствующий наименьшему . Элементы разрешающей строки делим на разрешающий элемент.
     Составим  симплексную таблицу:
cj базис (xj)
аi0 7 5 0 0 0
х1 х2 х3 х4 х5
0 0
0
x3 x4
x5
35 42
49
2
4
3
3 2
5
1 0
0
0 1
0
0 0
1
35/2 21/2
49/3
  z 0 -3 -3 0 0 0  
0 3
0
x3 x1
x5
14 42/4
70/4
0 1
0
2
1/2

7/2
1 0
0
-1/2 1/4
-3/4
0 0
1
14 21
5
  z 126/4 0 -7/2 0 3/4 0  
0 3
3
x3 x1
x2
4 8
5
0 1
0
0 0
1
1 0
0
-1/14 10/28
-6/28
-4/7 -1/7
2/7
 
  z 39 0 0 0 3/7 3/7  
 
   Исходное  опорное решение:
    
x1 = (0, 0, 35, 42, 49);
z1 = 0. 

   В оценочной строке две отрицательные  оценки -3 и -3. Выбрать нужно столбец  с наименьшей отрицательной оценкой, т.к. они равны, выбираем любую. Выбираем столбец, соответствующий х1. Разрешающую строку выбираем по:
 

     Этот  минимум достигается для 2-й строки. В базис вводим х1, выводим из базиса х4. В результате первого шага получаем второе опорное решение: 

x2 = ;
z2 =
.
 

     В оценочной строке одна отрицательная  оценка -7/2, соответствующая столбцу  x2. Разрешающую строку выбираем по:
     

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

 хопт = (8, 5, 4, 0, 0);
zmax = 39. 

   Оптимальное решение исходной задачи получается отбрасыванием из компонент, связанных с балансовыми переменными х3, х4, х5, т.е.
   
= (8,5).

     При этом значение zmax не изменится.
     Решим задачу геометрически. Рассмотрим систему неравенств, определяющих множество допустимых планов.
   1 + 3х2 35,
   4x1 + 2х2
42,

   1 + 5х2
49

     х1
0; x2
0.
 

     Построим  граничащие прямые:
     
x1 0 17.5
x2 11.66 0
 
     1 + 3х2 = 35, 

     
x1 0 10,5
x2 21 0
 
     4x1 + 2х2 = 42, 

     
x1 0 16,33
x2 9,8 0
 
     1 + 5х2 = 49,               
        

     Поскольку х1 0 и x2 0, то допустимые планы принадлежат неотрицательному многоугольнику, при этом вся область лежит левее т.к. точка О(0;0) принадлежит области:


 

     Областью  решения системы является четырехугольник  ОАВС.
     Целевая функция z = 3x1 + 3x2. Линии уровня целевой функции z задаются уравнением:
   1 + 5х2 = const. 

     Это семейство параллельных прямых. Вектор N(3;3) является целевым, он перпендикулярен линиям уровня. Он указывает направление возрастания функции z. Вершина многоугольника, через которую проходит последняя линии уровня, дает максимальное значение целевой функции. На рисунке 1видно, что это точка В, которая лежит на пересечении прямых:
     
4x1 + 2х2
42,
 

1 + 5х2
49.
 

     Решив систему уравнений получим координаты точки В х1 = 8, х2 = 5. Подставив это значение в целевую функцию, получим .
     Ответ: Оптимальным планом выпуска продукции А и В является выпуск 8 ед. и 5 ед. продукции соответственно, при этом предприятие получает наибольшую прибыль, которая составляет 39 тыс. рублей. Остатки ресурсов равны нулю.
 

    ДВОЙСТВЕННОСТЬ  В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ.
          
     Для модели предыдущей задачи составить  двойственную, из симплексной таблицы найти ее решение и проверить по основной теореме.
     Решение: Экономической сутью переменных двойственной задачи является определение оценок на ресурсы.
     Для данной задачи составим двойственную.
z = 3x1 + 3x2
  

   1 + 3х2 35,   y1
   1 + 2х2
42,   y2

   1 + 5х2
49,   y3

   х1
0; x2
0

     Получим:           
     w = 35y1 +42y2 +49y3

    2y1 + 4y2 +3y3 3   x1
   3y1 + 2y2 + 5y3
3   x2

   yi
0 (i=1, 2, 3)

     Соответствие  между переменными исходной и  двойственной задачами:
      x3   x4   x5
     
     y1   y2   y3 

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

    Проверка. .
   Ответ: Наиболее дефицитным являются сырье 2 и 3 вида. Наименее дефицитным является сырье 1.
 


    ТРАНСПОРТНАЯ  ЗАДАЧА.
 
      Дано: Из пунктов Ai, i= нужно перевезти ai, i= единиц груза соответственно, в пункты Bj, j= в количествах bj, j= соответственно. Затраты на перевозку 1 единицы груза из пункта Ai в Bj заданы в виде матрицы С=((сij)).
       
 
 

     Найти: Найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.
     Решение: По методу «северо – западного» угла оптимальный план имеет вид:
Bj B1 B2 B3 B4 B5
Аi 100 55 125 40 55
A1   90 7     5     4     3     2
90
A2   10 4   55 3   85 8     7     6
150
A3     2     2   40 5   35 6     9
75
A4     2     5     6   5 6   55 7
60
 
 
     Число базисных клеток m+n – 1=4+5 – 1=8. Затраты на данный план:
     

     По  методу наименьшего элемента оптимальный  план приобретет вид:
Bj B1 B2 B3 B4 B5 Ui
Аi 100 55 125 40 55
A1 8   7 6   5 0   4   35 3   55 2 0
90
A2 1   4 0 +20 3   -125 8   5 7 0   6 4
150
A3   40 2   - 35 2 -2 + 5 0   6 4   9 3
75
A4   60 2 3   5 -1   6 0   6 2   7 3
60
Vj -1 -1 4 3 2  
 
     Число заполненных клеток  m+n – 1=8. Затраты:

     С помощью метода потенциалов проверим, оптимален ли план перевозок. Определим потенциалы строк – Ui и столбцов – Vj удовлетворяющие условию: Ui + Vj = Cij для базисных переменных (для занятых клеток). Зададим U1=0.
    U1+V4=3               U1=0                  V1=-1
   U1+V5=2               U2=4                  V2=-1
   U2+V2=3               U3=3                  V3=4
   U2+V3=8               U4=3                  V4=3
   U2+V4=7                                          V5=2
   U3+V1=2
   U3+V2=2
   U4+V1=2 

     Определим характеристики для свободных неизвестных (пустых клеток) по формуле Eij = Cij – (Ui + Vj) и запишем в левом нижнем углу свободных клеток. План оптимален, если все Eij 0.
   E11=7-(0-1) > 0,
   E12=5-(0-1) > 0,
   E13=4-(0-4) = 0,
   E21=4-(4-1) > 0,
   E25=6-(4+2) = 0,
   E33=5-(3+4) = - 2,
   E34=6-(3+3) = 0,
   E35=9-(3+2) > 0,
   E42=5-(3-1) > 0,
   E43=6-(3+4) = - 1,
   E44=6-(3+3) = 0,
   E45=7-(4+2) > 0. 

     Имеем две клетки с отрицательными оценками, выбираем с наименьшей оценкой E33. Строим контур для клетки А3В3:
 А33
А23
А22
А32.
 

     Вершинам  присваиваем чередующиеся знаки  плюс – минус, выбираем наименьшую поставку Количество груза в ''положительных'' вершинах увеличивается на 35, а в ''отрицательных'' уменьшается на 35. ?min(35;125)=35 ,?z=-2*35=-70 Получаем следующий план перевозок: 

Bj B1 B2 B3 B4 B5 Ui
Аi 100 55 125 40 55
A1 6   7 6   5 0   4   35 3   55 2 -4
90
A2 -1   4   55 3   90 8   5 7 0   6 0
150
A3   40 2 2   2   35 5 2   6 6   9 -3
75
A4   60 2 5   5 1   6 2   6 4   7 -3
60
Vj 5 3 8 7 6  
 
     План  не оптимален т.к. Е21<0. Z=1580-70=1510
     ?min(40;90)=40 ,?z=-1*40=-80. Получим следующий план:
Bj B1 B2 B3 B4 B5 Ui
Аi 100 55 125 40 55
A1 7   7 6   5 0   4   35 3   55 2 -4
90
A2   40 4   55 3   50 8   5 7 0   6 0
150
A3
и т.д.................


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


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


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


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


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