Решение задач симплексным методом

Автор работы: Пользователь скрыл имя, 12 Ноября 2009 в 18:52, Не определен

Описание работы

1.Краткий обзор алгоритмов решения задач данного типа
2.Содержательная постановка задачи
3.Разработка и описание алгоритма решения задачи
4.Назначение программы
5.Инструкция пользователю
6.Текст исходного модуля

Файлы: 2 файла

simpleks_metod1.xls

— 118.00 Кб (Просмотреть файл, Скачать файл)

курсовик.doc

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

       Построение  математической модели осуществляется в три этапа :

       1. Определение переменных, для которых  будет составляться математическая модель.

         Так как требуется определить  план производства изделий А и В, то переменными модели будут:

        x1 - объём производства изделия А, в единицах;

         x2 - объём производства изделия В, в единицах.

       2. Формирование целевой функции.

         Так как прибыль от реализации  единицы готовых изделий А  и В известна, то общий доход от их реализации составляет 2x1 + 3x2 ( рублей ). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции : определить допустимые значения переменных x1 и x2 , максимизирующих целевую функцию F = 2x1 + 3x2 .

       3. Формирование системы ограничений.

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

        x1 + 5x2 £ 10 ; 3x1 + 2x2 £ 12 ; 2x1 + 4x2 £ 10 .

         Так как объёмы производства  продукции не могут принимать  отрицательные значения, то появляются ограничения неотрицательности :

        x1 ³ 0 ; x2 ³ 0 .

         Таким образом, математическая  модель задачи представлена в виде : определить план x1 , x2 , обеспечивающий максимальное значение функции :

       max F = max ( 2x1 + 3x2 )

         при наличии ограничений :

        x1 + 5x2 £ 10 ;

       3x1 + 2x2 £ 12 ;

       2x1 + 4x2 £ 10 .

       x1 ³ 0 ; x2 ³ 0 .

3.2 Решение задачи  вручную

       Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.

       1. Приведение задачи к форме  :

       x1 + 5x2 £ 10 ;

       3x1 + 2x2 £ 12 ;

       2x1 + 4x2 £ 10 .

       x1 ³ 0 ; x2 ³ 0 .

       2. Канонизируем систему ограничений  :

       x1 + 5x2 + x3 = 10 ;

       3x1 + 2x2 + x4 = 12 ;

       2x1 + 4x2 + x5 = 10 .

       x1 ³ 0 ; x2 ³ 0 .

       A1 A2 A3 A4 A5 A0

       3. Заполняется исходная симплекс-таблица  и рассчитываются симплекс-разности по формулам :

       d0 = - текущее значение целевой функции

       
                         C        2        3        0        0        0
       Б        Cб        A0        A1        A2        A3        A4        A5
       A3        0        10        1        5        1        0        0
       A4        0        12        3        2        0        1        0
       A5        0        10        2        4        0        0        1
                d        0        -2        -3        0        0        0

       di = - расчёт симплекс-разностей, где j = 1..6 .

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

       4. Определяем направляющий столбец  j*. Для задачи на max он определяется минимальной отрицательной симплекс-разностью. В данном случае это вектор А2

       5. Вектор i*, который нужно вывести из базиса, определяется по отношению :

       min при аi j > 0

       В данном случае сначала это А3 .

       5. Заполняется новая симплекс-таблица  по исключеню Жордана - Гаусса :

         а). направляющую строку i* делим на направляющий элемент :

       a i j = a i j / a i j , где j = 1..6

         б). преобразование всей оставшейся части матрицы :

       a ij = aij - a i j × aij , где i ¹ i* , j ¹ j*

       
                         C        2        3        0        0        0
       Б        Cб        A0        A1        A2        A3        A4        A5
       A2        3        2        1/5        1        1/5        0        0
       A4        0        8        13/5        0        -2/5        1        0
       A5        0        2        6/5        0        -4/5        0        1
                d        6        -7/5        0        3/5        0        0

       В результате преобразований получаем новую  симплекс-таблицу :

       Повторяя  пункты 3 - 5, получим следующие таблицы :

                         C        2        3        0        0        0
       Б        Cб        A0        A1        A2        A3        A4        A5
       A2        3        5/3        0        1        1/3        0        -1/6
       A4        0        11/3        0        0        4/3        1        -13/6
       A1        2        5/3        1        0        -2/3        0        5/6
                d        8 1/3        0        0        -1/3        0        7/6
       
                         C        2        3        0        0        0
       Б        Cб        A0        A1        A2        A3        A4        A5
       A2        3        3/4        0        1        0        -1/4        3/8
       A3        0        11/4        0        0        1        3/4        -13/8
       A1        2        7/2        1        0        0        1/2        -1/4
                d        9 1/4        0        0        0        1/4        5/8

       Так как все симплекс-разности положительны, то оптимальное решение найдено :

       X = ( 7/2 , 3/4 , 11/4 , 0 , 0 ) ( единиц )

       max F = 9 1/4 ( рублей )

 

4.НАЗНАЧЕНИЕ ПРОГРАММЫ

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

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

 

5.ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ

       Задание условий

       Все условия задаются в колонке “A”  первого листа(программа результат помещает в лист 2)

       В третьей строке(”A3″) необходимо записать целеыую функцию на минимум или  максимум(min или max после =) например:

       3×1+2×2+4×3+2×4=min

       В 5 строке необходимо записать количество знаков в дробной части чисел(или  ничего то есть пусто или пробел(ы) )

       начиная с 9 строки записываются ограничения  по одной строке на каждое ограничениe. Hапример:

6×2+6×3+4×4=60 
2×1+4×2+8×3+8×4<=80 
4×1+4×2+12×4>=20 
2×1+6×2+2×3+8×4=30 
(можно выделить и занести все ограничения нашего примера в буфер и вставить в ячейку “9А”, программа автоматически разместит их в строчки, что располагаются ниже.)Содержимое последней строки ограничений(В нашем примере A13) должно быть пусто или пробел(ы) Переменные Xi по умолчанию считается не отрицательными.

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

       Получение результата

       Результат работы располагается на втором листе книги.

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

Информация о работе Решение задач симплексным методом