Мегаобучалка Главная | О нас | Обратная связь  


Затраты на одно изделие




ЦЕНТРАЛЬНЫЙ МЕЖРЕГИОНАЛЬНЫЙ ТЕХНИКУМ ОТРАСЛЕВЫХ  ТЕХНОЛОГИЙ И ПРЕДПРИНИМАТЕЛЬСТВА

 

 

Утверждаю

Зам. директора по учебной части

 

 


                                                                                 «  »                 200 г.

ЗАДАНИЕ

на курсовое проектирование

по предмету «Математические методы»

 

Студенту: Сергееву Евгению Анатольевичу.

Тема проекта: «Линейное программирование, решение задач симплексным методом».

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

 

Введение                                                                                                

Теоретическая часть                                                                            

Практическая часть                                                                            

Задачи и их решение:

 

Задача первая:

Решить задачу симплекс методом:

 

         

    X1+3X2≤300

               X1+X2≤150

           X1≥0

           X2≥0

 

     F = 2X1+3X2 → max

 

3.1.2 Задача вторая:

 

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



 

 

Виды сырья

 

Расход сырья на продукцию

Запасы сырья

1 2
1 1 3 20
2 2 1 10
3 2 2 17
Прибыль 2 1  

 

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?

 

3.1.3. Задача третья:

 

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

 

 

Виды сырья

 

Расход сырья на продукцию

Запасы сырья

1 2 3
1 2 3 7 1250
2 1 1 0 250
3 5 3 0 900
Прибыль 41 35 96  

 

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?

 

3.1.4. Задача четвертая:

          

Для изготовления 4 видов продукции используются 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:

 

 

Виды сырья

 

Расход сырья на продукцию

Запасы сырья

1 2 3 4
1 2 3 3 1 20
2 1 1 2 2 11
3 1 2 3 1 25
Прибыль 2 4 3 2  

 

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?

 

Заключение                                                                                                 

Список литературы                                                                             

                  Председатель цикловой комиссии                                    /Баранов В.А.

Руководитель курсового проекта                                                                 /Карпушкин А.Г.

                                                                                                                             

 

             Дата выдачи задания:                                                                                                   Срок окончания:

              « »                              2007 г.                                             « »                         2007 г.

 

 

СИМПЛЕКСНЫЙ МЕТОД

 

    Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским ученым

Л В.Канторовичем.

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

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

элемента:

• способ определения какого-либо первоначального допустимого

базисного решения задачи;

• правило перехода к лучшему (точнее, не худшему) решению;

• критерий проверки оптимальности найденного решения.

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

 

Обыкновенные жордановы исключения

 

  Рассмотрим систему из m линейных уравнений с n неизвестными

 

                 a11x1 + a12x2 + … + a1nxn = b1,

                 ……………

                 am1x1 + am2x2 + … + amnxn = bm.

 

  Запишем эту систему в виде таблицы

 

  x1 xj xn
b1 =

a11 … a1j … a1n

 

………………..

bi =

ai1 … aij … ain

 

………………..

bm =

am1 … amj … amn

 

   Шагом обыкновенного жорданова исключения (ОЖИ), произведенным над данной таблицей с разрешающим элементом aij ≠ 0 с I разрешающей строкой и j разрешающим столбцом, назовем операцию решения уравнения

 

   bi = ai1x1 + ai2x2 + … + aijxj + … + ainxn

 

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

  Нетрудно проверить, что новая таблица будет иметь вид

 

  x1 x2 bi xn
b1 =

b11 b12 … a1j … b1n

b2 =

b21 b22 … a2j … b2n

………………..

xj

 -ai1    –ai2 … 1... -ain

………………..

bm =

bm1 bm2 … amj … bmn

 

: aij,

где brs = arsaij - arjais (i ≠ r, j ≠ s),

 

причем все элементы таблицы нужно разделить на aij.

  Таким образом, один шаг жорданова исключения (ШЖИ) переводит исходную таблицу в новую по схеме, состоящей из следующих 5 правил:

1) разрешающий элемент заменяется единицей

2) остальные элементы разрешающего столбца j остаются без изменения.

3) остальные элементы разрешающей строки i меняют лишь свои знаки.

4) остальные элементы  brs вычисляются по формуле  brs = arsaij - arjais

5) все элементы новой таблицы делятся на разрешающий элемент aij.

 

 

Пример 1. Для таблицы

 

  X1 X2 X3
Y1 = 1 -2 3
Y2 = -1 1 2
Y3 = 2 -1 -1

 

один шаг жорданова исключения с разрешающими 2-й строкой и 3-м столбцом приводим к таблице                 

 

  X1 X2 Y2
Y1 = 5 -7 3
X3 = 1 -1 1
Y3 = 3 -1 -1

 

: 2

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

 

Модифицированные жордановы исключения

     Если исходную систему уравнений ai1x1 + ai2x2 + … + ainxn = bi, где i = 1,m,   

 

записать в виде –ai1(-x1) – ai2(-x2) - … - ain (-xn) = bi

 

и составить таблицу

 

 

  -X1 -X2 …-Xn
b1 = –a11 –a12 … –a1n
….

…………..

bm = –am1 –am2 … –amn

 

то в этих случаях вместо ОЖИ пользуются МЖИ.

Один шаг МЖИ с разрешающим элементом “-ars”, означает переход к новой таблице

 

  -X1 -Yr -Xn
b1 = b11  ... a1s  … b1n
….

…………………….

xs = -ar1  … 1   … -ar n
….

…………………….

bm = bm1 ams bmn

 

: (-ars)

которая получается по правилам 1 – 5 ОЖИ с тем лишь изменением, что правила 2 и 3 меняются ролями:

1) остальные элементы разрешающей строки остаются без изменения

2) остальные элементы разрешающего столбца меняют лишь свои знаки

Рассмотрим систему

 

2X1 + 3X2 – 5X3 = 16 = b1,   

3X1 - 2X2 + 4X3 = 36 = b2,   

5X1 + 7X2 – 11X3 = 44 = b3.

 

Запишем ее в виде таблицы

 

   

  -x1 -x2 -x3
b1 = -2 -3 5
b2 = -3 2 -4
b3 = -5 -7 11

 

 

и произведем один шаг МЖИ с разрешающим элементом “2”

 

  -x1 -b2 -x3
b1 = -13 3 -2
x2 = -3 1 -4
b3 = -31 7 -6

 

: 2


Экстремумы линейной функции

 

     Пусть рассматривается общая задача линейного програм­мирования. Воснове вычислительных методов ЛП лежит следующая фундаментальная теорема.

     Теорема. Если задача линейного программирования име­ет оптимальное решение

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

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

     Данная теорема утверждает, что существует по край­ней мере одно опорное оптимальное решение, однако, в за­дачах могут встретиться несколько опорных оптимальных решений (альтернативный оптимум).

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

 

1. С помощью ЖИ найдем все опорные решения систе­мы.

 

a11x1 + a12x2 + … + a1nxn = b1,

……...................

ak1x1 + ak2x2 + … + aknxn = bk,

ak+1,1x1 + ak+1,2x2 + … + ak+1nxn ≤ bk+1,

……...................

am1x1 + am2x2 + … + amnxn ≤ bm.

 

2. Вычислим для каждого из них значение функции Z, определяемое соотношением.

 

   Z = c1x1 + c2x2 + … + cnxn.

 

3. Выберем из них экстремальное Z.

 

   Следует отметить, что может оказаться очень большое число опорных решений, поэтому нужно производить упо­рядоченный перебор опорных решений, добиваясь на

каж­дом шаге монотонного изменения функции Z.

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

 

Симплексный метод на основе полных таблиц

 

Постановка задачи об определении оптимального ассортимента продукции

 

   Предприятие может производить два вида изделий А и В, располагая для их изготовления ограниченными ресурса­ми материала чугуна и стали соответственно в количествах 350 и 392 кг и оборудования в количестве 408 станко-часов. Данные, представленные в виде таблицы, характеризуют затраты каждого из перечисленных трех видов ресурсов на изготовление одного изделия А и В.

Требуется определить сколько изделий А и В должно про­изводить предприятие, чтобы достичь наибольшей прибыли.

 

 

Виды ресурсов

Объем ресурсов

 

Затраты на одно изделие

А В
 Чугун 350 14 5
 Сталь 392 14 8
 Оборудование 408 6 12
 Прибыль в руб.   10 5

 

   Введем искомые неизвестные Х1 и X2, обозначающие число изделий А и В, которые должно производить пред­приятие.

   Тогда математически задачу можно сформулировать сле­дующим образом.

Среди множества неотрицательных решений системы неравенств

 

   14X1 + 5Х2 ≤ 350,    (1.1)

   14Х1 + 8Х2 ≤ 392,

   6Х1 + 12Х2 ≤ 408,

 

найти такое решение, для которого функция

 

   Z = 10 Х1 + 5 Х2

 

достигает наибольшего значения.

 

Геометрическое решение задачи

 

   Прежде всего, построим область допустимых решений, соответствующую системе неравенств.

  Для этого, заменив каждое из неравенств равенством

 

         14Х1 + 5Х2 = 350, (1-я прямая),

         14X1 + 8Х2 = 392, (2-я прямая),

         6Х1 + 12Х2 = 408, (3-я прямая),

 

строим граничную линию. Учитывая, что Х1 ≥ 0 и Х2 ≥ 0, полу­чаем заштрихованную часть плоскости, образующую много­угольник решений OABCD (рис.1).

   Затем строим линию уровня 10Х1 + 5Х2 = 0 и вектор (10;5), которые взаимно перпендикулярны. Нетрудно показать, что вектор дает направление наибольшего возрастания линей­ной функции.

   Действительно

 

Z0 = 10X10 + 5Х20 = 10 * 0 + 5 * 0 = 0,

ZА = 10X1A + 5Х2A = 10 * 0 + 5 * 34 = 170,

ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 и т. д.

 

    Из всех линий уровня выбираем две, из которых одна проходит через точку 0 и дает min значение функции Z, а другая проходит через точку С и функция Z для нее прини­мает mах значение. Эти линии уровня называются опорными.

 

 

 

 


Рис. 1

 

   Точка C образована первой и второй прямыми. Следова­тельно, решая систему уравнений

 

   14Хl + 5Х2 = 350,

   14Х1 + 8Х2 = 392,

 

найдем координаты точки C

 

    Х1 = 20, Х2 = 14,

 

при этом Zmax = 10 * 20 + 5 * 14 = 270 руб.

   Таким образом, mах прибыль в 270 руб. будет получена, если предприятие произведет 20 изделий вида А и 14 изде­лий вида В.

 

Отыскание максимума линейной функции

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

Добавляя к левой части неравенств

 

   14X1 + 5Х2 ≤ 350,

   14Х1 + 8Х2 ≤ 392,

   6Х1 + 12Х2 ≤ 408,

 

некоторую нео­трицательную величину Yj ≥ 0 (i = 1, 2, 3),      (1.2)

называемую выравнивающей или базисной переменной, пре­вратим их в уравнения:

 

 

 

  14  Х1 + 5Х2 + У1    = 350,
  14  Х1 + 8Х2 + У2  = 392,
  6  X1 + 12Х2     + У3  = 408,
  -10  X1 - 5Х2    + Z = 0.
         

 

 

 

 

 

(1.3)
 

 

   При этом можно показать, что каждому решению систе­мы неравенств (1.1) соответствует единственное решение си­стемы уравнений (1.3) и неравенств (1.2) и наоборот.

 

   Каждая из переменных Y1, У2, У3 входит только в одно уравнение и зависит от переменных Х1 и X2, которые мы на­зываем свободными.

Системе (1.3) соответствует исходное допустимое базис­ное решение X1 = X2 = 0; 

Y1 = 350; Y2 = 392; Y3 = 408 и Z = 0.

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

   Первое уравнение делим на разрешающее число и вы­писываем получившееся уравнение. Умножая это уравнение на 14, 6 и -10 и вычитая соответственно из 2-го, 3-го и 4-го уравнений системы (1.3), придем к следующей системе (1.4):

 

 

  X1 +  5/14

 X2 + 1/4 Y1                      = 25,

 

3  Х2 – Y1 + Y2    = 42,
 

 

138/14  X2 – 6/14 Y1          + У3  = 258,
  -20/14  X2 + 10/14 Y1  + Z = 250.
         

 

 

 
(1.4)

 

       

 

 

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

   Таким образом, симплексное преобразование выполня­ется по следующему правилу:

 

1. Выбирается разрешающий столбец, соответствующий наименьшему отрицательному           элементу в Z - строке.

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

3. Элементы разрешающей строки делятся на разрешаю­щее число.

4. Вычисляются элементы всех остальных строк по фор­муле:

 

Новые эл-ты

=

Старые эл-ты

 

_

соответствующее число в разрешающей строке

 

*

соответствующее число в разре­шающем столбце

разрешающее число

 

 
 

 

                   

                                                                                                                                  

 

     Из системы (1.4) находим второе допустимое базисное решение Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, которому соответствует новое увеличенное значение функции Z = 250.

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

 

1. Если в Z - строке найдется хотя бы один отрицатель­ный элемент и

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

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

2. Если все элементы в Z - строке неотрицательны, то достигнуто оптимальное решение.

    Это и есть достаточные условия существования оптималь­ного плана решения.

В системе (1.4) коэффициент при Х2 в Z - строке отри­цательный, поэтому второй столбец будет разрешающим. Находим, что вторая строка будет разрешающей. Далее про­изводим симплексное преобразование системы (1.4) соглас­ном указанному правилу:

 

     X1 + 8/42 Y1 – 5/42 Y2 = 20,

     X2 – 1/3 Y1 + 1/3 Y2 = 14,

    20/7 Y1 – 23/7 Y2 + Y3 = 120,

    10/42 Y1 + 20/42 Y2 + Z = 270,  (1.5)

 

           Так как в Z - строке все элементы неотрицательны, то данный план является оптимальным. При этом Yl = Y2 = 0; X1 = 20; Х2 = 14 и Zmax = 270.

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

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

       Соответственно исходной системе уравнений (1.3) состав­ляем первую симплекс-таблицу (табл. 1.1).

 

    X1 X2 Y1 Y2 Y3 контр. столбец
Y1 350 14 5 1 0 0 370
Y2 392 14 8 0 1 0 415
Y3 408 6 12 0 0 1 427
 Z 0 -10 -5 0 0 0 -15

 

 

Таблица 1.1

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

Из табл. 1.1 имеем первое допустимое решение системы (1.3) Х1 = Х2 = 0, Y1 = 350,

Y2 = 392, Y3 = 408, Z = 0, которое соответствует вершине О (0,0) многоугольника допустимых решений OABCD (рис.1).

Переход ко второй симплекс-таблице (табл. 1.2) выпол­няется согласно указанному в этом пункте правилу для сим­плексных преобразований систем уравнений, при этом раз­решающая переменная Х1 идет в базис вместо разрешающей переменной Y1 Получаем табл. 1.2.

 

    X1 X2 Y1 Y2 Y3 контр. столбец
X1 25 1 5/14 1/14 0 0 370/14
Y2 42 0 3 -1 1 0 45
Y3 258 0 138/14 -6/14 0 1 3758/14
 Z 250 0 -20/14 10/14 0 0 3490/14

 

 

Таблица 1.2

 

      После заполнения табл. 1.2 следует проверить правиль­ность ее заполнения, для чего суммируем коэффициент по строкам и эта сумма должна быть равна коэффициентам, сто­ящим в соответствующих клетках контрольного столбца. Из табл. 1.2 второе допустимое решение будет Х1 = 25, Х2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 и Z = 250.

     Нетрудно видеть, что эта таблица соответствует систе­ме (1.4), а опорное решение

Х1 = 25, Х2 = 0 соответствует вершине D(25,0) многоугольника решений.

     Так как в Z - строке имеется отрицательный элемент, то улучшаем решение, для чего составляем симплексную табл. 1.3.

 

    X1 X2 Y1 Y2 Y3 контр. столбец
X1 20 1 0 4/21 -5/42 0 295/14
X2 14 0 1 -1/3 1/3 0 15
Y3 120 0 0 20/7 -23/7 1 844/7
 Z 270 0 0 5/21 10/21 0 1895/7

 

 

Таблица 1. 3

 

 

* Примечание. Для простоты вычислений следует помнить, что в новой таб­лице на месте элементов разрешающего столбца (кроме разрешающего элемента) стоят нули. Если в разрешающей строке стоят нули, то в новую таблицу соответствующие столбцы переносятся без изменения:

 

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

Табл. 1.3 соответствует системе уравнений (1.5) и опти­мальному решению Х1 = 20,

Х2 = 14 и Zmax = 270 и вершине С (20,14) многоугольника допустимых решений OABCD.

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

        

 

Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Читайте также:
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...
Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас...
Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней...
Почему наличие хронического атрофического гастрита способствует возникновению и развитию опухоли желудка?



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (102)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.103 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7