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

Наибольшие положительные  коэффициенты в z-строке при переменных х₇, и х₈ (2М-2/3), выбираем переменную х₇, это будет вводимая в базис переменная и ведущий столбец. Исключаемой из базиса переменной является R₃, так как для нее отношение решения к элементу ведущего столбца = 12/2 = 6 будет минимальным (для х₂ это соотношение = 13), это ведущая строка.

Новая ведущая строка = текущая  ведущая строка / ведущий элемент.

х₇ = (0 0 0 1 0 1 2 2 1 0 0 -1 0 0 1 12) / 2 = (0 0 0 1/2 0 1/2 1 1 1/2 0 0 -1/2 0 0 1/2  6)

Новая строка = текущая строка – (ее коэффициент в ведущем столбце  х новую ведущую строку).

z-строка: (0 0 0 М-1/3 0 М-1/3 2М-2/3 2М-2/3 М-1/3 -1/3 -1/3 -М 1/3-М 1/3-М 0 12М+31/3)

– (2М-2/3) х (0 0 0  1/2  0    1/2        1              1        1/2      0      0  -1/2     0        0  1/2      6) =

            = (0 0 0     0     0      0         0             0         0     -1/3 -1/3 -1/3 1/3-М 1/3-М 1/3-М 43/3)

х₁ = (1 0 2/3 2/3 1/3 0 0 1/3 1/3 -1/3 0 0 1/3 0 0  6) – 0 х (0 1 1/3 0 2/3 2/3 1/3 0 1/3 0 -1/3 0 0 1/3 0  13/3) = (1 0 2/3 2/3 1/3 0 0 1/3 1/3 -1/3 0 0 1/3 0 0  6)

х₂ = (0 1 1/3 0 2/3 2/3 1/3 0 1/3 0 -1/3 0 0 1/3 0  13/3) – 1/3 х (0 0 0 1/2 0 1/2 1 1 1/2 0 0 -1/2 0 0 1/2  6) = (0 1 1/3 -1/6 2/3 1/2 0 -1/3 1/6 0 -1/3 1/6 0 1/3 -1/6  7/3)

Базис	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	х11	х12	R1	R2	R3	Ответ
z	0	0	0	0	0	0	0	0	0	-1/3	-1/3	-1/3	1/3-М	1/3-М	1/3-М	43/3
х1	1	0	2/3	2/3	1/3	0	0	1/3	1/3	-1/3	0	0	1/3	0	0	6
х2	0	1	1/3	-1/6	2/3	1/2	0	-1/3	1/6	0	-1/3	1/6	0	1/3	-1/6	7/3
х7	0	0	0	1/2	0	1/2	1	1	1/2	0	0	-1/2	0	0	1/2	6

В полученной симплекс –  таблице все коэффициенты в z-уравнении имеют неположительные значения, значит, полученное на данном этапе решение является оптимальным и вычисления закончены.

z_min = 43/3

х₁ = 6

х₂ = 7/3

х₇ = 6

 

ОТВЕТ:

z_min = 43/3

х (6; 7/3; 0; 0; 0; 0; 6; 0; 0).

 

ПРОВЕРКА:

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

3х₁ + 2х₃ + 2х₄ + х₅ + х₈ + х₉ 18            3х6 =18 18 (условие выполняется)

3х₂ + х₃ + 2х₅ + 2х₆ + х₇ + х₉ 13            3х7/3 + 6 = 13 13 (усл. выполняется)

х₄ + х₆ + 2х₇ + 2х₈ + х₉ 12                      2х6 = 12 12 (условие выполняется)

х₁, х₂, х₃, х₄, х₅, х₆, х₇,х₈, х₉ 0.                6 0; 7/3 0; 6 0 (усл. выполняется)

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

Отходы, полученные при  раскрое алюминия, составят:

100 L (6 + 7/3 + 6) - 1364 L = 1433,33 L - 1364 L = 69,33 L.

 

 

4. Вывод.

Таким образом, интерпретируя  полученные результаты, минимальное необходимое количество материала при выполнении заказа составит 43/3 рулона алюминия стандартной шириной 100мм, оптимальный вариант раскроя материала – сочетание вариантов

№1 – 6 рулонов (на заготовку 30х30мм - колпачок №1),

№2 – 7/3 рулона (на заготовку 32х32мм - колпачок №2),

№7 – 6 рулонов (на заготовку 32х32мм - колпачок №2 и на заготовку 34х34мм - колпачок №3).

Как видно из результатов  проверки полученные значения являются минимальными возможными при заданных условиях, значит оптимизация (минимизация) затрат материала достигнута.

Надо заметить, что количество рулонов материала получилось дробное число, что на практике невозможно, так как раскрой производится гильотиной одновременно всего рулона.

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

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

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

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

 

 

 

 

 

 

 

 

Список литературы.

 

1. Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2005.

2. Нит И.В. Линейное программирование. – М.: Издательство Московского университета, 1978.

3. Фомин Г.П. Методы и модели линейного программирования в коммерческой деятельности. – М.: Финансы и статистика, 2000.

4. Волков И.К., Загоруйко  Е.А. Исследование операций. Учебник для вузов – М.: МГТУ им.Баумана, 2004.

5. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. Учебное пособие для вузов. – М.: Дрофа, 2006.