В системе ограничений перейдем от неравенств к равенствам. Введем неотрицательные переменные x и x

  • ID: 33616 
  • 6 страниц

Фрагмент работы:

№1.

В системе ограничений перейдем от неравенств к равенствам. Введем неотрицательные переменные x3 и x4, такие, что

x1+x3=1

x2+x4=2

Т.к. на переменные x1 и x2 не наложено условие неотрицательности, то представим их в виде разности 2 положительных переменных: [image], [image].

Тогда каноническая форма исходной задачи линейного программирования будет иметь вид:

[image]-[image]-[image]+[image]®max

[image]

Найдем решение исходной задачи, используя графическую интерпретацию. Построим графики граничных прямых и определим область допустимых решений:

[image]

Исходя из рисунка видно, что областью допустимых решений является неограниченная снизу область ABC. Для нахождения оптимального решения отобразим на графике целевую функцию Z в виде линий уровня. При этом нулевому значению целевой функции будет соответствовать точка (0;0). Будем перемещать линию уровня параллельно самой себе в направлении перпендикулярного ей вектора grad Z=(1;-1), насколько это возможно. При этом видно, что перемещение возможно до бесконечности по лучу BC. Таким образом, на данной системе ограничений целевая функция не ограничена.

№2.

Найдем решение задачи, используя графическую интерпретацию. Построим графики граничных прямых и определим область допустимых решений:

[image]

Исходя из рисунка видно, что областью допустимых решений является неограниченная сверху область ABC. В этой области возможно только одно базисное решение: точка B. найдем ее координаты:

[image] [image]

№3.

Получим общее решение системы ограничений задачи методом Жордана-Гаусса:

Новый вид задачи

Z=-5x1+6x3-5x5+10®max

[image]

Разрешенный вид:

[image]

Составляем симплекс-таблицу:

Разрешающий столбец третий, разрешающая строка первая

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

x1=0 x2=3 x3=0 x4=0 x5=1,4 x6=0

Zmax=3

№4.

Запишем данные задачи в виде матрицы перевозок.

Проверим, является ли задача закрытой:

[image]=4+6+10+10=10

[image]=7+7+7+7+2=30