logo
Глава 3

3.4 Вопросы и упражнения

  1. Дайте определение опорного плана задачи линейного программирования.

  2. В чем заключается идея симплекс-метода?

  3. Как строится симплексная таблица?

  4. Сформулируйте критерий оптимальности симплексной таблицы.

  5. Сформулируйте критерий допустимости симплексной таблицы.

  6. Сформулируйте правило выбора разрешающего элемента.

  7. Сформулируйте признак неограниченности целевой функции (по симплексной таблице).

  8. Может ли задача линейного программирования, удовлетворяющая условиям, перечисленным в разделе 3.2, быть неразрешимой по причине того, что ее ОДП пуста?

  9. Если критерий оптимальности нарушен в нескольких столбцах, в чем заключается способ выбора разрешающего столбца, при котором решение может быть получено быстрее?

  10. Нельзя ли найти способ (и в чем он заключается) определения по заключительной симплексной таблице того, является ли полученное решение единственным?

  11. Решите симплекс-методом следующие задачи:

    Пример 1.

    max -4х1 + 3х2 - 3х3

    -2х1 + х2 + х3 = 1

    х1 - 3х2 - х4 = -13

    4х1 + х2 + х5 = 26

    -х1 - 3х2  -6

    х1-5  0

    Пример 2.

    min -3х2 + 2х3

    4х1 + 10х2 - 5х3  7

    0,5х1 - 3х2 + х4 = 4

    3х1 +12х2 - 8х3  3

    х1-4  0

    Пример 3.

    max 5х2 - 2х4

    4х1 + 10х2 - 5х3  7

    х1 - 3х2 + 2х3 + х4 4

    3х1 - 8х2  12

    х1-4  0

    Пример 4.

    max 2х1 + х2 - х3 + 5х4

    х1 + 7х2 + х3 + 7х4  46

    4х1 - х2 + х3 + 2х4  8

    2х1 + 3х2 - х3 + х4 10

    х1-4  0

  12. Решите симплекс-методом задачу 9 из раздела 1.5.

*Симплекс представляет собой выпуклую оболочкуm+1 аффинно независимых точек вm-мерном пространстве (т.е. пересечение всех выпуклых множеств, содержащих эти точки). Не приводя здесь определение аффинной независимости, ограничимся утвержением, что вm-мерном пространстве таких точек может быть не большеm+1. Можно сказать, что любой треугольник на плоскости (в двумерном пространстве) - симплекс.

Название метода связано с тем, что изначально он был разработан для задачи, ОДП которой представляло собой так называемый стандартный симплекс (определялось ограничениями ;xi 0,i=1,n). На плоскости это треугольник с вершиной в начале координат и точках (0;1) и (1;0).

*Вектора А1 . . . Аn называются линейно независимыми, если не существует таких чисел d1 . . . dn, не равных одновременно нулю, при которых djАj = 0.

*Число сочетаний изnпоmрассчитывается по формуле.

*Знак $ при вводе формул вMicrosoftExcelозначает абсолютную ссылку. В дальнейшем при копировании формулы номер столбца или строки, перед которыми стоит этот знак, не будет изменяться.

71