8  Симплекс алгоритъм (илюстрация)

Да разгледаме прост пример за оптимизационна задача, която може да бъде решена с помощта на симплекс алгоритъма. Нека имаме следната линейна програма, например за максимизиране на печалбата от производство два вида козунак (и двата вида изискват определени количества от два вида ресурси: брашно и захар):

\max z(x_1, x_2) = x_1 + 1.5x_2 при следните ограничения:

\begin{align*} \quad x_1 + 2 x_2 & \leq 10 \quad \text{брашно (кг.)} \\ \quad x_1 + x_2 & \leq 8 \quad \text{захар (кг.)} \\ \quad x_1, x_2 & \geq 0 \\ \end{align*}

Покажи 
# | fig-cap: "Целева функция и допустимо множество"

# | code-fold: true


import numpy as np

import plotly.graph_objects as go


# Допустими върхове за задачата:

# x1 + 2x2 <= 10

# x1 + x2 <= 8

# x1, x2 >= 0

vertices = [(0, 0), (8, 0), (6, 2), (0, 5)]

vertices_x = [point[0] for point in vertices]

vertices_y = [point[1] for point in vertices]

vertices_z = [0] * len(vertices)


fig = go.Figure()


# Върхове на допустимото множество в равнината z = 0

fig.add_trace(
    go.Scatter3d(
        x=vertices_x,
        y=vertices_y,
        z=vertices_z,
        mode="markers+text",
        marker=dict(size=4, color="red"),
        text=[f"({x}, {y}, 0)" for x, y in vertices],
        textposition="top center",
        name="Върхове",
    )
)


# Ребра на допустимото множество

for index in range(len(vertices)):

    next_index = (index + 1) % len(vertices)

    fig.add_trace(
        go.Scatter3d(
            x=[vertices[index][0], vertices[next_index][0]],
            y=[vertices[index][1], vertices[next_index][1]],
            z=[0, 0],
            mode="lines",
            line=dict(color="blue", width=4),
            showlegend=False,
        )
    )


# Нормален вектор на целевата функция z = x1 + 1.5x2.

# В x-y равнината това е градиентът (1, 1.5).

normal_start = np.array([0.8, 0.6, 0.0])

normal_vector = np.array([1.0, 1.5, 0.0])

normal_scale = 1.5

normal_end = normal_start + normal_scale * normal_vector


fig.add_trace(
    go.Scatter3d(
        x=[normal_start[0], normal_end[0]],
        y=[normal_start[1], normal_end[1]],
        z=[0, 0],
        mode="lines+text",
        line=dict(color="orange", width=8),
        text=[None, "n = (1, 1.5)"],
        textposition="top center",
        name="Нормален вектор",
    )
)


fig.add_trace(
    go.Cone(
        x=[normal_end[0]],
        y=[normal_end[1]],
        z=[0],
        u=[normal_vector[0]],
        v=[normal_vector[1]],
        w=[0],
        anchor="tip",
        sizemode="absolute",
        sizeref=0.45,
        colorscale=[[0, "orange"], [1, "orange"]],
        showscale=False,
        name="Нормален вектор",
    )
)


# Мрежа за целевата функция z = x1 + 1.5x2

x1 = np.linspace(0, 8, 40)

x2 = np.linspace(0, 8, 40)

X1, X2 = np.meshgrid(x1, x2)

Z = X1 + 1.5 * X2


fig.add_trace(
    go.Surface(
        x=X1,
        y=X2,
        z=Z,
        opacity=0.55,
        colorscale="Viridis",
        name="z = x1 + 1.5x2",
        showscale=False,
    )
)


# Ниво под оптимума: z = 6

z_plane_1 = 6

intersection_x_1 = np.linspace(0, z_plane_1, 200)

intersection_y_1 = (z_plane_1 - intersection_x_1) / 1.5

mask_1 = (intersection_y_1 >= 0) & (intersection_y_1 <= 8)

intersection_x_1 = intersection_x_1[mask_1]

intersection_y_1 = intersection_y_1[mask_1]


fig.add_trace(
    go.Surface(
        x=X1,
        y=X2,
        z=np.full(X1.shape, z_plane_1),
        opacity=0.18,
        colorscale="Blues",
        showscale=False,
    )
)


fig.add_trace(
    go.Scatter3d(
        x=intersection_x_1,
        y=intersection_y_1,
        z=[z_plane_1] * len(intersection_x_1),
        mode="lines",
        line=dict(color="crimson", width=5),
        name="z = 6",
    )
)


fig.add_trace(
    go.Scatter3d(
        x=intersection_x_1,
        y=intersection_y_1,
        z=[0] * len(intersection_x_1),
        mode="lines",
        line=dict(color="crimson", width=3, dash="dash"),
        showlegend=False,
    )
)


# Оптимално ниво: z = 9, достигнато в точка (6, 2)

z_plane_2 = 9

intersection_x_2 = np.linspace(0, z_plane_2, 200)

intersection_y_2 = (z_plane_2 - intersection_x_2) / 1.5

mask_2 = (intersection_y_2 >= 0) & (intersection_y_2 <= 8)

intersection_x_2 = intersection_x_2[mask_2]

intersection_y_2 = intersection_y_2[mask_2]


fig.add_trace(
    go.Surface(
        x=X1,
        y=X2,
        z=np.full(X1.shape, z_plane_2),
        opacity=0.18,
        colorscale="Greens",
        showscale=False,
    )
)


fig.add_trace(
    go.Scatter3d(
        x=intersection_x_2,
        y=intersection_y_2,
        z=[z_plane_2] * len(intersection_x_2),
        mode="lines",
        line=dict(color="darkgreen", width=6),
        name="z = 9",
    )
)


fig.add_trace(
    go.Scatter3d(
        x=intersection_x_2,
        y=intersection_y_2,
        z=[0] * len(intersection_x_2),
        mode="lines",
        line=dict(color="darkgreen", width=3, dash="dash"),
        showlegend=False,
    )
)


# Оптимална точка
fig.add_trace(
    go.Scatter3d(
        x=[6],
        y=[2],
        z=[9],
        mode="markers+text",
        marker=dict(size=6, color="black"),
        text=["Оптимум (6, 2, 9)"],
        textposition="top center",
        name="Оптимум",
    )
)


fig.update_layout(
    title="Целева функция и допустимо множество",
    scene=dict(
        xaxis_title="Козунак 1",
        yaxis_title="Козунак 2",
        zaxis_title="Печалба",
        xaxis=dict(range=[0, 8]),
        yaxis=dict(range=[0, 8]),
        zaxis=dict(range=[0, 12]),
        aspectmode="cube",
    ),
    showlegend=False,
)


fig.show()
Фигура 8.1