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

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

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

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

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

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

Скачать целиком (178.84 Кб) Сколько стоит заказать работу?
Содержимое работы - 1 файл

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

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

     Содержание 

Задача 1. Нахождение оптимального объема производства изделий  3

Задача 2. Задача об оптимальном использовании ресурсов    8

Задача 3. Задача о межотраслевом балансе             12

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

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

     Задача 1.

     Нахождение  оптимального объема производства изделий.

     Условие. Процесс изготовления двух видов промышленных изделий состоит в последовательной обработке каждого из них на трех станках (таблица 1). Время использования этих станков для производства данных изделий ограничено 10-ю часами в сутки.

     Время обработки и прибыль от продажи  одного изделия

                   Таблица 1

Изделие Время обработки  одного изделия, мин. Удельная прибыль, $
       Станок 1 Станок 2 Станок 3       
1 10      6 8      2
2 5      20 15      3
 

     Найти оптимальный объем производства изделий каждого вида. 

     Решение.

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

     Определим максимальное значение целевой функции F(X) = 2x1+3x2 при следующих условиях-ограничениях:

      10x1+5x2≤600

      6x1+20x2≤600

      8x1+15x2≤600

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

      10x1 + 5x2 + 1x3 + 0x4 + 0x5 = 600

      6x1 + 20x2 + 0x3 + 1x4 + 0x5 = 600

      8x1 + 15x2 + 0x3 + 0x4 + 1x5 = 600

     Матрица коэффициентов A = a(ij) этой системы уравнений  имеет вид: 

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

     Решим систему уравнений относительно базисных переменных:

     x3, x4, x5,

     Полагая, что свободные переменные равны 0, получим первый опорный план (таблица 2):

     х1 = (0,0,600,600,600)

               таблица 2

 План  Базис  В  x1  x2  x3  x4  x5
 0  x3  600  10  5  1  0  0
     x4  600  6  20  0  1  0
     x5  600  8  15  0  0  1
Индексная строка  F(X0)  0  -2  -3  0  0  0

      

     Переходим к основному алгоритму симплекс-метода (таблица 3)

                              Таблица 3

План Базис  В  x1  x2  x3  x4  x5  min
 1  x3  600  10  5  1  0  0  120
     x4  600  6  20  0  1  0  30
     x5  600  8  15  0  0  1  40
Индексная строка  F(X1)  0  -2  -3  0  0  0  0

       
 

     Итерация  №0.

     Текущий опорный план неоптимален, так как  в индексной строке находятся  отрицательные коэффициенты

     В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.

     Вычислим  значения Di по строкам как частное от деления 

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

     Следовательно, 2-ая строка является ведущей (таблица 4):

                                                                                  Таблица 4

План Базис  В  x1  x2  x3  x4  x5  min
2  x3  450  8.5  0  1  -0.25  0  52.94
     x2  30  0.3  1  0  0.05  0  100
     x5  150  3.5  0  0  -0.75  1  42.86
Индексная строка  F(X2)  90  -1.1  0  0  0.15  0  0

      

     Итерация  №1.

     Текущий опорный план неоптимален, так как  в индексной строке находятся  отрицательные коэффициенты

     В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.

     Вычислим  значения Di по строкам как частное от деления 

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

     Следовательно, 3-ая строка является ведущей (таблица 5)

      

                              Таблица 5

План Базис  В  x1  x2  x3  x4  x5  min
3  x3  85.71  0  0  1  1.57  -2.43  54.55
     x2  17.14  0  1  0  0.1143  -0.0857  150
     x1  42.86  1  0  0  -0.2143  0.2857  0
Индексная строка  F(X3)  137.14  0  0  0  -0.0857  0.3143  0

      

     Итерация  №2.

       Текущий опорный план неоптимален,  так как в индексной строке  находятся отрицательные коэффициенты

       В качестве ведущего выберем  столбец, соответствующий переменной x4, так как это наибольший коэффициент.

       Вычислим значения Di по строкам как частное от деления 

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

       Следовательно, 1-ая строка является  ведущей. Конец итераций: найден оптимальный план. Окончательный вариант симплекс-таблицы (таблица 6):

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