3.2 Пример 2

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

Строим область допустимых решений, градиент и одну из линий уровня.

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

3.3. Пример 3

3. Решить задачу линейного программирования:

Строим прямые линии, соответствующие неравенствам системы ограничений и находим полуплоскости, являющиеся областями решений этих неравенств.

Область допустимых решений задачи является пустым множеством. Задача не имеет решения ввиду несовместности системы ограничений.

3.4. Пример 4

Задача. Ткацкая фабрика располагает 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₁₀ из уравнений ограничений и подставим в целевую функцию. Исходная симплекс – таблица примет вид:

Таблица 3.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, вычтем из второй строки четвертую. Получим таблицу.

Таблица 3.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.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. Получим таблицу.

Таблица 3.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. Получим таблицу.

Таблица 3.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.

Ответ: 100 станков первого типа производит ткань 1 вида

200 станков второго типа производит ткань 1 вида

190 станков первого типа производит ткань 2 вида.

Прибыль при этом составляет 9960 руб. Ткань первого вида выпускается по плану 2700 м, а второго вида больше на 120 м.