Тема: Симплекс-метод

  • Вид работы:
    Контрольная работа
  • Предмет:
    Математика
  • Язык:
    Русский
  • Формат файла:
    MS Word
  • Размер файла:
    11,46 Кб
Симплекс-метод
Симплекс-метод
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Произвести распил 5 - метровых бревен на брусья размерами 1,5; 2,4; 3,2 м в отношении 1:2:3 так, чтобы минимизировать общую величину отходов.

Решение

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

Способы Распила iПолучаемые брусьяКоличество бревен, распиливаемых по i-му способу отходы 1.5 2.4 3.21 2 3 43 1 1 00 1 0 20 0 1 0x1 x2 x3 x40.5 1.1 0.3 0.2

Количество бревен, распиливаемых по каждому способу, обозначим х1, х2, х3, х4 соответственно. Составим математическую модель задачи. Поскольку общее количество бревен, поступающих на распил, неизвестно, будем искать их количество в процентах. Тогда

x1234=1 (где 1 означает 100%).

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

Учитывая количество брусьев каждого размера, получаемых при распиле одним из четырех способов и условие комплектности (1:2:3), получим следующие уравнения:

x123=х - для брусьев длиной 1.5 м;

х2+2х4=2х- для брусьев длиной 2.4 м;

х3=3х- для брусьев длиной 3.2 м.

Из последнего уравнения , подставив в предыдущие уравнения, получим

или

При этом

Общая величина отходов составит . Необходимо найти минимум этой функции при заданных условиях.

Итак, имеем задачу линейного программирования:


Из второго уравнения системы ограничений следует, что х123=0, а при четвертом способе распила получаются только бруски в 2.4 м, что не удовлетворяет условию задачи. Таким образом данная задача не имеет допустимых решений.


Способы Распила iПолучаемые брусьяКоличество бревен, распиливаемых по i-му способу отходы 1.5 2.4 3.21 2 3 4 5 6 7 83 1 1 0 2 1 0 00 1 0 2 0 0 1 00 0 1 0 0 0 0 1x1 x2 x3 x4 х5 х6 х7 х80.5 1.1 0.3 0.2 2 3.5 2.6 1.8

Запишем новую систему ограничений, учитывая условие комплектности


При этом

Функция отходов примет вид

.

Получаем следующую задачу линейного программирования:


Решим ее симплекс методом.

Будем искать . Запишем данные задачи в таблицу.

)

Базисные переменныех1х2х3х4х5х6х7х8bi¾111111111¾3102100¾0120010-F0.51.10.30.223.52.61.80

Элементы таблицы (коэффициенты при х) обозначим

Найдем начальное базисное решение.

) Выбираем четвертый столбец разрешающим.

Вычислим симплекс-отношения для положительных элементов четвертого столбца и выберем наименьшее полученное число

Элементы второй строки делим на а34=2.

Элементы четвертого столбца заменяем 0.

На месте а34 ставим 1.

х4 переходит в столбец базисных переменных.

Остальные элементы таблицы пересчитываем по формуле ,

где - разрешающий элемент.

Базисные переменныех1х2х3х4х5х6х7х8bi¾10.50110.51¾310210400.51000.50-F0.510.367023.52.51.8670

) Выберем шестой столбец. Находим , тогда разрешающий элемент а26=1.

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

Базисные переменныех1х2х3х4х5х6х7х8bi¾-2-0.50-100.56310210400.51000.50-F-10-2.5-1.970-502.53.0340

4) Теперь нужно записать базисную переменную в первую строку. В восьмом столбце единственный положительный элемент , поэтому а18= - разрешающий.

Базисные переменныех1х2х3х4х5х6х7х8biх8-1.2-0.30.40-0.600.310.6х62.60.90.801.810.100.2х4-0.40.4-0.21-0.200.600.2-F-6.36-1.59-3.180-3.1801.590-1.82

Получили первоначальное базисное решение х4=0.2, х6=0.2, х8=0.6, х12357=0, F(х)=1.82. Это решение не является оптимальным, поскольку в F - строке есть отрицательные элементы.

) Перейдем к новому решению.

Наибольший по модулю отрицательный элемент в F - строке - это -6.36. Поэтому разрешающий столбец - первый.

Единственный положительный элемент в первом столбце а21=2.6, он и будет разрешающим.

х1 занимает место х6 среди базисных переменных. Далее выполняем еще один шаг симплекс-метода и получаем новую таблицу.

Базисные переменныех1х2х3х4х5х6х7х8biх800.1150.76900.2310.4610.34610.692х110.3460.30800.6920.3850.03800.077х400.538-0.07710.0770.1540.61500.231-F00.612-1.22301.2232.4464.770-1.33

) Полученное решение не является оптимальным, поскольку в последней строке есть отрицательный элемент. Третий столбец разрешающий. Находим симплексное отношение : . Разрешающий элемент а23=0.308.

Базисные переменныех1х2х3х4х5х6х7х8biх8-2.5-0.2300-1.5-0.50.2510.5х33.251.12101.271.250.1200.25х40.250.63010.250.250.6300.25-F42004450-1.025


х3=0.25, х4=0.25, х8=0.5, х12567=0, .

Ответ: чтобы выполнить условие задачи, необходимо 25% бревен распиливать третьим способом, 25%- четвертым способом и 50% восьмым способом. При этом минимальная средняя величина отходов составит 1.025 м с каждого бревна.

Похожие работы

 

Не нашел материала для курсовой или диплома?
Пишем качественные работы
Без плагиата!