Реализация симплекс-метода в случае положительных свободных членов

Автор работы: Пользователь скрыл имя, 17 Января 2012 в 13:49, курсовая работа

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

Цель нашей работы состоит в том, чтобы определить план выпуска продукции для получения максимальной прибыли, чтобы сырьё II вида было израсходовано полностью. Оценить каждый из видов сырья, используемых для производства продукции.

Прикрепленные файлы: 1 файл

2Курсовик по Мат Мет2.docx

— 71.02 Кб (Скачать документ)

     В качестве параметров режима задаются ограничения по времени поиска решения  в секундах (Максимальное время) (максимально 32767), количеству итераций (Предельное число итераций), точности соответствия результата заданному значению (Относительная  погрешность), допустимого отклонения экстремума от оптимального значения при использовании режима целочисленной  математики (Допустимое отклонение), а  также условие прекращения поиска экстремума (Сходимость), задающее величину относительного приращения экстремума за последние пять итераций.

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

     Решением  задачи является рассчитываемый надстройкой  Поиск решения набор переменных X = (x1, x2 ,..., xn), обеспечивающий максимальное (минимальное, заданное) значение целевой  функции E(x1, x2 ,..., xn).

     Следующим этапом при подготовке задачи к решению  является программирование математических выражений, связывающих между собой  исходные числовые данные и вычисляемые выражения. Электронные таблицы Excel позволяют записывать в выбранную ячейку не только числа, но и математические выражения, составленные по общим правилам языков программирования с использованием символа присваивания =, знаков операций (+,–,*,/) и встроенных функций. В качестве операндов в таких выражениях могут использоваться константы или имена ячеек Excel.

     Использование современных информационных технологий при решении прикладных производственных задач является актуальнейшим требованием  нашего времени и освобождает  от рутинной вычислительной работы по реализации математических методов  что заметно повышает «коэффициент полезного действия» затраченного времени. 

 

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

   3.1.Построение математической модели:

 

           Система ограничений, в которой x1, x2 >= 0:

                 x2+x3<= 8

                 x1+x2<= 5

                 2x2 +x3<= 12

           Целевая функция:

                 Z = 1x1 + 5x2   + 2x3 → max

   3.2.Приводим  задачу к каноническому  виду:

 

Введем  дополнительные переменные х4 , х5 , х6 

     x2+x34= 8

     x1+x25= 5

      2x2 +x36 = 12 

Начальный опорный план 

х0=(0, 0, 0, 8, 5, 12) 

z0=z(x0)=1*0+5*0+2*0=0 

z0-z=-1x1-5x2-2x3→ min 
 
 
 
 

F(X)= 1 X1 + 5 X2 + 2 X3 (max)

 
Ограничения:

0 X1 + 1 X2 + 1 X3 + X4 = 8
1 X1 + 1 X2 + 0 X3 + X5 = 5
0 X1 + 2 X2 + 1 X3 + X6 = 12

Xi≥0 

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

Базисные 
переменные
Свободные 
члены
X1 X2 X3 X4 X5 X6
X4 8 0 1 1 1 0 0
X5 5 1 1 0 0 1 0
X6 12 0 2 1 0 0 1
z0-z 0 -1 -5 -2 0 0 0
 

      Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-5). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

 
Пересчитаем таблицу

Базисные 
переменные
Свободные 
члены
X1 X5 X3 X4 X5 X6
X4 3 -1 -1 1 1 -1 0
X2 5 1 1 2 0 1 0
X6 2 -2 -2 1 0 -2 1
z0-z 25 4 5 -2 0 5 0
 

       Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-2). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца. 

 
Пересчитаем таблицу

     
Базисные 
переменные
Свободные 
члены
X1 X5 X6 X4 X5 X6
X4 1 1 1 -1 1 1 -1
X2 5 1 1 0 0 1 0
X3 2 -2 -2 1 0 -2 1
z0-z 29 0 1 2 0 1 2

      
 
          Так как в столбце «Свободные члены» нет отрицательных элементов, то найдено допустимое решение. Так как в строке «z0-z» тоже нет отрицательных элементов, то найдено допустимое решение.

Найдено оптимальное решение 
 
 
 
 
 
 
 
 

   3.3.Блок-схема

 

 

 

 

   3.4.Анализ решения.

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

    В результате получены следующие результаты:

         - сырье первого вида =5 л. ; 

         -  план выпуска продукции =58,25;

          -  сырье второго вида = 8 л. 

    В ходе решения задачи было построено 3 симплексные таблицы:

    1. Первая симплексная таблица была построена по исходным данным;
    2. В результате построения второй симплексной таблицы было вычислено максимальное количество ед. сырья второго вида = 8 л.;
    3. В результате построения третьей симплексной таблицы было вычислено максимальное количество ед. сырья первого вида =0,75 л.;
    4. Т. к. в третьей симплексной таблице в строке целевой функции все элементы стали оптимальными, завершили решение;
    5. Из третьей симплексной таблицы выписываем необходимые данные: количество сырья первого и второго вида. После чего высчитываем максимальный план выпуска продукции – подставляя в целевую функцию полученные в ходе решения данные (8 и 0,75 ) и получаем 43 цен.ед.

 

4.Литература:

 
    1. Петросян  Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. – М., 1998.
    2. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, 1985.
    3. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.– М.: Наука, 1981.

 

5.Вывод

 

      В данной курсовой работе я представил метод решения «Реализация симплекс-метода в случае положительных свободных членов».

       Мы достигли цели работы которая состояла в том, чтобы определить план выпуска продукции для получения максимальной прибыли, чтобы сырьё II вида было израсходовано полностью. Оценить каждый из видов сырья, используемых для производства продукции. 
 
 

Информация о работе Реализация симплекс-метода в случае положительных свободных членов