Задача №1. Линейная производственная задача.

Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известны технологическая матрица А затрат любого ресурса на единицу каждой продукции, вектор В объемов ресурсов и вектор С удельной прибыли

4 0 8 7 316

А= 3 2 5 1 В= 216 С=(31, 10, 41, 29)

5 6 3 2 199

Найти производственную программу (х1, х2, х3, х4), максимизирующую прибыль

z=31х1+10х2+41х3+29х4

Затраты ресурсов 1-го вида на производственную программу

4х1+0х2+8х3+7х4≤316

Затраты ресурсов 2-го вида на производственную программу

3х1+2х2+5х3+х4≤216

Затраты ресурсов 3-го вида на производственную программу

5х1+6х2+3х3+2х4≤199

Имеем

4х1+0х2+8х3+7х4≤316

3х1+2х2+5х3+х4≤216 (1)

5х1+6х2+3х3+2х4≤199

где по смыслу задачи

х1≥0, х2≥0, х3≥0, х4≥0. (2)

Получена задача на нахождение условного экстремума. Для ее решения систему неравенств (1) при помощи дополнительных неизвестных х5, х6, х7 заменим системой линейных алгебраических уравнений

4х1+0х2+8х3+7х4+х5=316 (I)

3х1+2х2+5х3+ х4+х6=216 (II) (3)

5х1+6х2+3х3+2х4+х7=199 (III)

где дополнительные переменные имеют смысл остатков соответствующих ресурсов, а именно

х5 – остаток сырья 1-го вида,

х6 – остаток сырья 2-го вида,

х7 – остаток сырья 3-го вида.

Среди всех решений системы уравнений (3), удовлетворяющих условию неотрицательности

х1≥0, х2≥0, х3≥0, х4≥0, х5≥0, х6≥0, х7≥0 (4)

надо найти то решение, при котором функция

z=31х1+10х2+41х3+29х4

будет иметь наибольшее значение

Организуем направленный перебор базисных решений при помощи симплекс метода.

Из функции z(x) видно, что наиболее выгодно начать производство с 3-го ресурса.

Найдем ведущее уравнение:

bi 316 216 199 316

min ------- = ----- ----- ----- = -----

ai3>0 8 5 3 8

Примем I-е уравнение за ведущее. Решаем симплекс методом: