Решение

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

Пусть x_j – объем выпуска предприятием продукции j -го (j = 1,..., 4) вида. Тогда математическая модель задачи будет иметь вид:

F _max = 4 х ₁ + 3 х ₂ + 6 х ₃ + 7 х ₄ ® max;

2 х ₁ + х ₂ + х ₃ + х ₄ £ 280;

х ₁ + х ₃ + х ₄ £ 80;

х ₁ + 2 х ₂ + х ₃ £ 250;

х ₁ ³ 0; х ₂ ³ 0; х ₃ ³ 0; х ₄ ³ 0.

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

F _max = 4 х ₁ + 3 х ₂ + 6 х ₃ + 7 х ₄ ® max;

2 х ₁ + х ₂ + х ₃ + х ₄ + х ₅ = 280;

х ₁ + х ₃ + х ₄ + х ₆ = 80;

х ₁ + 2 х ₂ + х ₃ + х ₇ = 250;

х ₁ ³ 0; х ₂ ³ 0; х ₃ ³ 0; х ₄ ³ 0; х ₅ ³ 0; х ₆ ³ 0; х ₇ ³ 0.

3. Симплексным методом найдем оптимальное решение задачи.

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

х ₁ = 0; х ₂ = 0; х ₃ = 0; х ₄ = 0; х ₅ = 280; х ₆ = 80; х ₇ = 250; F = 0.

Построим начальную симплекс-таблицу.

БП	Решение	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 5
x 6
x 7
F		–4	–3	–6	–7

Выберем столбец x ₄в качестве разрешающего, как содержащий в последней строке наименьшее отрицательное число.

Вычислим симплекс-отношения (отношения элементов столбца «Решение» к положительным элементам разрешающего столбца) для строк симплекс-таблицы

x ₅: 280 / 1 = 280;

x ₆: 80/ 1 = 80.

Строку x ₆ выберем в качестве разрешающей, как имеющую наименьшее симплекс-отношение.

На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

Вместо переменной x ₆ в базис вводится переменная x ₄.

Построчно пересчитываем симплекс-таблицу:

- вычисление новых элементов разрешающей строки (строка x ₄)

НЭР = СТЭ / РЭ

- вычисление новых элементов всех остальных строк

НЭ = СТЭ – К×НЭР,

где НЭ — элемент нового плана; СТЭ — элемент старого плана; РЭ — разрешающий элемент; К — коэффициент текущей строки в разрешающем столбце; НЭР — соответствующий новый элемент разрешающей строки.

x ₄: 80 / 1 = 80; 1 / 1 = 1; 0 / 1 = 0; 1 / 1 = 1; 1 / 1 = 1; 0 / 1 = 0; 1 / 1 = 1; 0 / 1 = 0;

x ₅: 280 – 1 ´ 80 = 200; 2 – 1 ´ 1 = 1; 1 – 1 ´ 0 = 1; 1 – 1 ´ 1 = 0;

1 – 1 ´ 1 = 0; 1 – 1 ´ 0 = 1; 0 – 1 ´ 1 = –1; 0 – 1 ´ 0 = 0;

x ₇: 250 – 0 ´ 80 = 250; 1 – 0 ´ 1 = 1; 2 – 0 ´ 0 = 2; 1 – 0 ´ 1 = 1;

0 – 0 ´ 1 = 0; 0 – 0 ´ 0 = 0; 0 – 0 ´ 1 = 0; 1 – 0 ´ 0 = 1;

F: 0 – (–7) ´ 80 = 560; –4 – (–7) ´ 1 = 3; –3 – (–7) ´ 0 = –3; –6 – (–7) ´ 1 = 1;

(–7) – (–7) ´ 1 = 0; 0 – (–7) ´ 0 = 0; 0 – (–7) ´ 1 = 7; 0 – (–7) ´ 0 = 0.

Получим

БП	Решение	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 5							–1
x 4
x 7
F			–3

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

Выберем столбец x ₂в качестве разрешающего, как содержащий в последней строке отрицательное число.

Вычислим симплекс-отношения для строк симплекс-таблицы

x ₅: 200 / 1 = 200;

x ₇: 250/ 2 = 125.

Строку x ₇ выберем в качестве разрешающей, как имеющую наименьшее симплекс-отношение.

На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

Вместо переменной x ₇ в базис вводится переменная x ₂.

Построчно пересчитываем симплекс-таблицу.

x ₂: 250 / 2 = 125; 1 / 2 = 0,5; 2 / 2 = 1; 1 / 2 = 0,5; 0 / 2 = 0; 0 / 2 = 0; 0 / 2 = 0; 1 / 2 = 0,5;

x ₅: 200 – 1 ´ 125 = 75; 1 – 1 ´ 0,5 = 0,5; 1 – 1 ´ 1 = 0; 0 – 1 ´ 0,5 = –0,5;

0 – 1 ´ 0 = 0; 1 – 1 ´ 0 = 1; –1 – 1 ´ 0 = –1; 0 – 1 ´ 0,5 = –0,5;

x ₄: 80 – 0 ´ 125 = 80; 1 – 0 ´ 0,5 = 1; 0 – 0 ´ 1 = 0; 1 – 0 ´ 0,5 = 1;

1 – 0 ´ 0 = 1; 0 – 0 ´ 0 = 0; 1 – 0 ´ 0 = 1; 0 – 0 ´ 0,5 = 0;

F: 560 – (–3) ´ 125 = 935; 3 – (–3) ´ 0,5 = 4,5; –3 – (–3) ´ 1 = 0; 1 – (–3) ´ 0,5 = 2,5;

0 – (–3) ´ 0 = 0; 0 – (–3) ´ 0 = 0; 7 – (–3) ´ 0 = 7; 0 – (–3) ´ 0,5 = 1,5.

Получим

БП	Решение	x 1	x 2	x 3	x 4	x 5	x 6	x 7
x 5		0,5		–0,5			–1	–0,5
x 4
x 2		0,5		0,5				0,5
F		4,5		2,5				1,5

Полученное базисное решение (Значения базисных переменных записаны в столбце «Решение». Все небазисные переменные равны нулю)

х ₁^* = 0; х ₂^* = 125; х ₃^* = 0; х ₄^* = 80; х ₅^* = 75; х ₆^* = 0; х ₇^* = 0; F ^* = 935

является оптимальным, так как в последней строке симплекс-таблицы нет отрицательных элементов.

Вывод: для того, чтобы получить максимальный доход в 935 ден. ед., предприятию необходимо производить 125 ед. продукции 2-го вида, 80 ед. продукции 4-го вида, продукцию 1-го и 3-го вида производить не рекомендуется.

4. Составим математическую модельдвойственной задачи.

Предположим, что предприятие решило остановить производство и продать имеющиеся запасы ресурсов некой фирме. Надо найти оценки стоимости этих ресурсов (цены на ресурсы) y_i (i = 1,..., 3) с учетом следующих требований, отражающих противоположные экономические интересы предприятия как владельца ресурсов и фирмы как покупателя ресурсов.

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

f = 280 y ₁ + 80 y ₂ + 250 y ₃ ® min.

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

2 y ₁ + y ₂ + y ₃ ³ 4;

y ₁ + 2 y ₃ ³ 3;

y ₁ + y ₂ + y ₃ ³ 6;

y ₁ + y ₂ ³ 7;

y ₁ ³ 0; y ₂ ³ 0; y ₃ ³ 0.