Задачи линейного программирования

Автор работы: Пользователь скрыл имя, 28 Декабря 2010 в 21:40, контрольная работа

Краткое описание

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

Содержание работы

Задача 1. Нахождение оптимального объема производства изделий 3
Задача 2. Задача об оптимальном использовании ресурсов 8
Задача 3. Задача о межотраслевом балансе 12
Задача 4. Задача линейного программирования симплексным методом 16
Список использованной литературы 21

Содержимое работы - 1 файл

Содержание1(2).doc

— 360.00 Кб (Скачать файл)

     Вычисление  вектора X = BY (3) производится с помощью операции умножения матриц, а в данном случае – умножения матрицы В на вектор Y. Для этого необходимо ячейки воспользоваться функцией МУМНОЖ. В открывшимся диалоговом окне появятся два свободных поля: Массив1 и Массив2. В Массив 1 заполняются данные матрицы В, а в Массив 2 вектор Y, после нажатия комбинации клавиш Ctrl+Shift+Enter, в соответствующих ячейках (D6:D7) появляется значение вектора Х.

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

     xij = aij xj,          (4)

     где aij – элементы матрицы А, расположенной в ячейках A2:B4, xj – элементы вектора Х, найденного выше и расположенные в ячейках D6:D7. Для проведения вычислений xij необходимо проделать следующее.

     1. Вычислить транспонированный вектор  Хт относительно вектора Х. При этом вектор-столбец Х станет вектором-строкой Хт. Это необходимо для согласования размерностей дальнейшего умножения элементов векторов. Для этого воспользуемся функцией ТРАНСП. В появившемся диалоговом окне ТРАНСП введем данные вектор Х (диапазон ячеек D6:D7) в рабочее поле Массив и после нажатия сочетания клавиш Ctrl+Shift+Enter увидим в соответствующих ячейках (D10:E10) транспонированный вектор Хт.

     2. Вычислим межотраслевые поставки продукции xij . Для этого проделать следующие операции:

     - в ячейке A12, в которой будет расположено значение x11, необходимо набрать формулу =А2*D10, которая означает, что x11 = a11 *x1 .Аналогично заполняются все ячейки массива A18:B19.

     В результате все межотраслевые поставки продукции будут найдены и  расположатся в матрице с ячейками A18:B19. Они показывают самый оптимальный вариант решения задачи. 

     
204 276
68 92

     Ответ:  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Задача 4.

     Задача линейного программирования симплексным методом

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

            F(X) = 3X1 + 5X2

      Х1 + 5Х2 > 5

      ЗХ1 - Х2   < 3,

      1 - ЗХ2 > -6,

      Х1 >0, Х > 0. 

     Решение.

     Решим прямую задачу линейного программирования симплекс-методом.  Поскольку в  правой части присутствуют отрицательные  значения, умножим соответствующие  строки на (-1). Определим максимальное значение целевой функции F(X) = 3x1+5x2 при следующих условиях-ограничениях:

x1+x2≥5

3x1-x2≤3

-2x1+3x2≤6

     Для построения первого опорного плана  систему неравенств приведем к системе  уравнений путем введения дополнительных переменных (переход к канонической форме).

1x1 + 1x2-1x3 + 0x4 + 0x5 = 5

3x1-1x2 + 0x3 + 1x4 + 0x5 = 3

-2x1 + 3x2 + 0x3 + 0x4 + 1x5 = 6

     Введем  искусственные переменные x.

1x1 + 1x2-1x3 + 0x4 + 0x5 + 1x6 = 5

3x1-1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 3

-2x1 + 3x2 + 0x3 + 0x4 + 1x5 + 0x6 = 6

     Для постановки задачи на максимум целевую  функцию запишем так:

F(X) =  - Mx6 => max

     Из  уравнений выражаем искусственные  переменные:

  x6 = 5-x1-x2+x3 ,

 которые подставим  в целевую функцию:

 F(X) = (1M)x1+(1M)x2+(-1M)x3+(-5M) => max

     Введем  новую переменную x0 = x1+x2.

     Выразим базисные переменные <6, 4, 5> через  небазисные.

x0 = -5+x1+x2-x3

x6 = 5-x1-x2+x3

x4 = 3-3x1+x2

x5 = 6+2x1-3x2

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

x0 = -5+x1+x2-x3

x6 = 5-x1-x2+x3

x4 = 3-3x1+x2

x5 = 6+2x1-3x2

     В качестве новой переменной выбираем x2. Вычислим значения D2 по всем уравнениям для этой переменной. 

 и из них  выберем наименьшее: 

     Вместо переменной x5 в план войдет переменная x2. Выразим переменную x2 через x5 и подставим во все выражения. После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = -3+1.67x1-x3-0.3333x5

x6 = 3-1.67x1+x3+0.3333x5

x4 = 5-2.33x1-0.3333x5

x2 = 2+0.6667x1-0.3333x5

     Полагая небазисные переменные x = (6, 4, 2) равными  нулю, получим новый допустимый вектор и значение целевой функции:

x = (-1.67, 0, 1, 0, 0.3333, 0), x0 = -3

x0 = -3+1.67x1-x3-0.3333x5

x6 = 3-1.67x1+x3+0.3333x5

x4 = 5-2.33x1-0.3333x5

x2 = 2+0.6667x1-0.3333x5

     В качестве новой переменной выбираем x1. Вычислим значения D1 по всем уравнениям для этой переменной. 

и из них выберем  наименьшее: 

     Вместо  переменной x6 в план войдет переменная x1. Выразим переменную x1 через x6 и подставим во все выражения. После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = -0-0x3-0x5-1x6

x1 = 1.8+0.6x3+0.2x5-0.6x6

x4 = 0.8-1.4x3-0.8x5+1.4x6

x2 = 3.2+0.4x3-0.2x5-0.4x6

     Полагая небазисные переменные x = (1, 4, 2) равными  нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, 0, 0, 0, 1), x0 = -0

     Выражение для x0 не содержит положительных элементов. Найден оптимальный план.

x0 = -0-0x3-0x5-1x6

x1 = 1.8+0.6x3+0.2x5-0.6x6

x4 = 0.8-1.4x3-0.8x5+1.4x6

x2 = 3.2+0.4x3-0.2x5-0.4x6

     На  этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.

x1 = 1.8+0.6x3+0.2x5

x4 = 0.8-1.4x3-0.8x5

x2 = 3.2+0.4x3-0.2x5

     Выразим базисные переменные:

x1 = 1.8+0.6x3+0.2x5

x2 = 3.2+0.4x3-0.2x5 ,

которые подставим  в целевую функцию:

F(X) = 3(1.8+0.6x3+0.2x5) + 5(3.2+0.4x3-0.2x5)

 или

F(X) = 21.4+3.8x3-0.4x5

     Получаем  новую систему переменных.

x0 = 21.4+3.8x3-0.4x5

x1 = 1.8+0.6x3+0.2x5

x4 = 0.8-1.4x3-0.8x5

x2 = 3.2+0.4x3-0.2x5

 

x0 = 21.4+3.8x3-0.4x5

x1 = 1.8+0.6x3+0.2x5

x4 = 0.8-1.4x3-0.8x5

x2 = 3.2+0.4x3-0.2x5

     В качестве новой переменной выбираем x3. Вычислим значения D3 по всем уравнениям для этой переменной. 

 и из них  выберем наименьшее: 

     Вместо  переменной x4 в план войдет переменная x3. Выразим переменную x3 через x4 и подставим во все выражения. После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = 23.57-2.71x4-2.57x5

x1 = 2.14-0.4286x4-0.1429x5

x3 = 0.5714-0.7143x4-0.5714x5

x2 = 3.43-0.2857x4-0.4286x5

     Полагая небазисные переменные x = (1, 3, 2) равными  нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, -0, 2.71, 2.57), x0 = 23.5714

     Выражение для x0 не содержит положительных элементов. Найден оптимальный план. Окончательный вариант системы уравнений:

x0 = 23.57-2.71x4-2.57x5

x1 = 2.14-0.4286x4-0.1429x5

x3 = 0.5714-0.7143x4-0.5714x5

x2 = 3.43-0.2857x4-0.4286x5

     Оптимальный план можно записать так:

x1 = 2.14

x3 = 0.5714

x2 = 3.43

F(X) = 3*2.14 + 5*3.43 = 23.57. 
 
 
 
 
 
 
 
 

Список  использованной литературы

  1. http://simplex-metod.narod.ru/real/prumery/page_4.html;
  2. http://www.reshmat.ru/example_simplex_1.html;
  3. Мадера А.Г. курс Математические модели в управлении – М:2005;
  4. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2004.

Информация о работе Задачи линейного программирования