Задание 1. Графоаналитический метод решения задач линейного программирования

Постановка задачи: Необходимо найти решение задачи, состоящей в определении максимального значения функции F=c1x1+c2x2, где переменные xj≥0 (j=1;2) – планируемое количество единиц j-й продукции, а сj – прибыль на единицу j-й продукции при условиях ai1x1+ai2x2≤bi (i=1,…,k), xj≥0 (j=1,2).

Решение

1. Заменяем ограничения-неравенства на ограничения-равенства (привести задачу к каноническому виду).

2. Построим прямые, соответствующие полученным уравнениям.

3. Определить полуплоскости, соответствующие заданным неравенствам в системе ограничений.

4. Поиск области допустимых решений задачи.

5. Построить градиент функции цели: grad F=(F’x1; F’x2).

6. Построить прямую нулевого уровня c1x1+c2x2=0, (эта прямая перпендикулярна градиенту).

7. Переместить эту прямую в направлении градиента, в результате чего будет найдена точка (точки), в которой целевая функция принимает максимальное значение, или же установлена неограниченность функции на множестве планов.

8. Определить координаты точки максимума функции и вычислить значение целевой функции в этой точке.

Система ограничений:

Целевая функция .

                               (1)

Построим прямые, ограничивающие многоугольник допустимых решений:

 

    
    
    

    
    
    

6

    
    
    

15

    
    
    
    
    

    
    
    

2

    
    
    

1

    
    

 

    
    
    

    
    
    

7

    
    
    

8

    
    
    
    
    

    
    
    

3

    
    
    

0

    
    

 

 - прямая, параллельная оси .

 - линия уровня (F=0);

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

Из системы неравенств (1) следует, что многоугольник решений на графике ОАВС.

Максимальную длину имеет перпендикуляр, опущенный из точки В, где пересекаются прямые

 - оптимальный план выпуска продукции.

 - максимальное значение прибыли.

Задание 2. Симплекс-метод решения задач линейного программирования

Постановка задачи: необходимо найти решение задачи, состоящей в определении максимального значения функции F=c1x1+c2x2+c3x3, где переменные xj≥0 (j=1;2) – планируемое количество единиц j-й продукции, а сj  прибыль на единицу j-й продукции при условиях ai1x1+ai2x2+…+ ainxn≤bi (i=1,…,m), xj≥0 (j=1,2,…,m).

Решение.

1. Записать математическую модель задачи

Сырье Продукция Общее количество сырья А В С

S1

15 12 15 360

S2

6 8 4 192

S3

3 2 5 180 Цена одного изделия (руб.) 9 10 16

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

3. Заполнить симплекс-таблицу.

4. Выяснить, имеется ли хотя бы одно отрицательное число Dj (в строке F, см. ............