X Международная студенческая научная конференция Студенческий научный форум - 2018

Пример 1

Задача. Ткацкая фабрика производит ткань двух артикулов. Для производства 10 тыс. м² ткани 1-го артикула фабрике необходимо 1 т тонковолокнистого и 3 т средневолокнистого хлопка, а для выпуска 100 тыс. м² ткани 2-го артикула – соответственно 5 и 6 т такого же хлопка. Поставки тонковолокнистого хлопка не превышают 80 т, а средневолокнистого – 150 т. По плану фабрика должна произвести не менее 60 тыс. м² ткани 1-го артикула и 800 тыс. м² ткани 2-го артикула. Прибыль фабрики от продажи 10 тыс. м² ткани 1-го артикула составляет 1,6 тыс. руб., а от продажи 100 тыс. м² ткани 2-го артикула – 6 тыс. руб. Предполагая, что вся произведенная ткань будет распродана, определить оптимальный план производства ткани, обеспечивающий получение наибольшей прибыли.

Решение. Для решения поставленной задачи необходимо построить её математическую модель. Осуществим это построение поэтапно.

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

2-й этап. Выберем управляемые переменные: х₁ – количество вырабатываемой ткани 1-го артикула (10 тыс. м²), х₂ – количество вырабатываемой ткани 2-го артикула (100 тыс. м²). Выбор разных единиц измерения для х₁ и х₂ позволяет выполнить весь последующий анализ в более удобном масштабе.

3-й этап. Осуществим выделение и формализацию ограничений. Это будут ограничения по количеству используемого средневолокнистого и тонковолокнистого хлопка, которые не могут превысить установленные размеры поставок, и ограничения по объемам производства, которые не могут быть ниже установленных плановых показателей. Общее необходимое количество тонковолокнистого хлопка при объемах производства ткани 1-го и 2-го артикулов х₁ и х₂ равно х₁ + 5х₂, а ограничение имеет вид

х₁ + 5х₂80.

Аналогичное ограничение для средневолокнистого хлопка

3х₁ + 6х₂150.

Ограничения, вытекающие из требования выполнения плана, имеют вид: х₁6, х₂8.

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

х₁0, х₂0.

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

F(x₁, x₂) = 1,6 x₁ + 6 x₂.

Все эти соотношения образуют оптимизационную математическую модель задачи, в которой необходимо найти такие х₁ и х₂, которые удовлетворяли бы всем ограничениям одновременно (были допустимыми) и при этом давали бы функции F(x₁, x₂) максимальное значение среди всех возможных допустимых x₁ и x₂. Эта модель и будет моделью линейного программирования.

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

Допустимой областью задачи является четырехугольник ABCD. На рис.1. построена линия уровня целевой функции для уровня с=9,6. Так как целевая функция максимизируется, то значение функции возрастает в направлении вектора . Приходим к выводу, что оптимальному решению отвечает точка С, координаты которой можно определить, решая совместно уравнения:

Отсюда х₁=30, х₂=10, при этом F=108.

Рис.1. Область допустимых решений

Пример 2

Задача. Ткацкая фабрика располагает 300 станков первого типа и 200 станков второго типа. Станки могут вырабатывать два вида ткани. Каждый вид станка может производить любой вид ткани, но в неодинаковом количестве. Станок первого типа производит в единицу времени 10 м ткани первого вида и 8 м ткани второго типа, а станок второго вида – соответственно 8 и 6 м ткани.

Каждый метр ткани первого вида приносит фабрике прибыль 2 руб. и второго вида – 3 руб. Согласно плану производства фабрика обязана выпустить в единицу времени не менее 2700 м ткани первого вида и 1400 – второго вида. Требуется так распределить загрузку станков, чтобы был выполнен план, и при этом прибыль в единицу времени была максимальной.

Решение. Введем обозначения: x₁, x₂ – число станков первого и второго типа, производящих ткань первого вида, x₃, x₄ – число станков первого и второго типа, производящих ткань второго вида.

Целевой функцией в этой задаче является общая прибыль предприятия:

F(x) = F(x₁, x₂, x₃, x₄) = 2(10x₁ + 8x₂) + 3(8x₃ + 6x₄) = 20x₁ + 16x₂ + 24x₃ + 18x₄

При этом должны выполняться следующие ограничения:

Решим задачу симплекс – методом. Введем дополнительные переменные x₅, x₆, x₇, x₈  0, так чтобы система неравенств превратилась в систему равенств. Ограничения примут вид:

Так как в системе ограничений нет очевидного базиса (т.е. нет решения, где бы базисные переменные были положительны), используем М – метод. Введем искусственные переменные x₉  0, x₁₀  0 для получения очевидного базиса. За использование этих переменных в целевой функции введем штраф -M(x₉ + x₁₀). Пусть для определенности М=100.Выразим x₉ и x₁₀ из уравнений ограничений и подставим в целевую функцию. Исходная симплекс – таблица примет вид:

Таблица .1

базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	Св.ч
F	1020	816	824	618	0	0	-100	-100	0	0	--
x5	1	0	1	0	1	0	0	0	0	0	300
x6	0	1	0	1	0	1	0	0	0	0	200
x9	10	8	0	0	0	0	-1	0	1	0	2700
x10	0	0	8	6	0	0	0	-1	0	1	1400

Т.к. F(x)  max, то избавляться надо от положительных слагаемых. Найдем отношения .Разрешающий элемент находится в четвертой строке первом столбце. Разделим четвертую строку на 10. Затем вычтем из первой строки четвертую, умноженную на 1020, вычтем из второй строки четвертую. Получим таблицу.

Таблица .2

базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	Св.ч
F	0	0	824	618	0	0	2	-100	-102	0	--
x5	0	-0,8	1	0	1	0	0,1	0	0,1	0	30
x6	0	1	0	1	0	1	0	0	0	0	200
x1	1	0,8	0	0	0	0	-0,1	0	0,1	0	270
x10	0	0	8	6	0	0	0	-1	0	1	1400

Найдем отношения Разрешающий элемент находится во второй строке третьем столбце. Вычтем из первой строки вторую, умноженную на 824, вычтем из пятой строки вторую, умноженную на 8. Получим таблицу.

Таблица 3

базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	Св.ч
F	0	659,2	0	618	-824	0	-80,4	-100	-19,6	0	--
x3	0	-0,8	1	0	1	0	0,1	0	-0,1	0	30
x6	0	1	0	1	0	1	0	0	0	0	200
x1	1	0,8	0	0	0	0	-0,1	0	0,1	0	270
x10	0	6,4	0	6	-8	0	-0,8	-1	0,8	1	1160

Найдем отношения 181, 25. Разрешающий элемент находится в пятой строке втором столбце. Вычтем из первой строки пятую, умноженную на 659,2; прибавим ко второй строке пятую, умноженную на 0,8; вычтем из третьей строки пятую; вычтем из четвертой строки пятую, умноженную на 0,8. Получим таблицу.

Таблица 4

базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	Св.ч
F	0	0	0	0	0	0	2	3	-102	-103	--
x3	0	0	1	0,75	0	0	0	-1/8	0	1/8	175
x6	0	0	0	1/16	5/4	1	1/8	5/32	-1/8	-5/32	75/4
x1	1	0	0	-3/4	1	0	0	1/8	0	1/8	125
x2	0	1	0	15/16	-5/4	0	-1/8	-5/32	1/8	5/32	725/4

Найдем отношения Разрешающий элемент находится в третьей строке девятом столбце. Разделим третью строку на Вычтем из первой строки третью, умноженную на 3; прибавим ко второй строке третью, умноженную на 1/8; вычтем из четвертой строки третью, умноженную на 1/8; прибавим к пятой строке третью, умноженную на 5/32. Получим таблицу.

Таблица 5

базис	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	Св.ч
F	0	0	0	-1,2	-24	-19,2	-0,4	0	-99,6	-100	--
x3	0	0	1	0,8	1	0,8	0,1	0	-0,1	0	190
x8	0	0	0	0,4	8	6,4	0,8	1	-0,8	-1	120
x1	1	0	0	-0,8	0	-0,8	-0,1	0	0,1	0	110
x2	0	1	0	1	0	1	0	0	0	0	200

Так как в строке для F нет положительных слагаемых, то оптимальное решение получено. Значения переменных:

x₁ = 110, x₂ = 200, x₃ = 190, x₄ = 0, x₅ = 0, x₆ = 0, x₇ = 0, x₈ =120, x₉ = 0, x₁₀=0. При этом значение функции равно F = 20x₁ + 16x₂ + 24x₃ + 18x₄ = 20110 +16200 + 24190 + 180 = 9960.

Код для цитирования: Скопировать