Целевая функция имеет вид

Приведем систему ограничений к виду основной задачи линейного программирования:

Пусть х1, х2 - свободные переменные, х3, х4, х5 - базисные.

Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:

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

Это решение является допустимым, но не опорным, т.к. присутствует отрицательный свободный член во второй строке. Ликвидируем его путём замены базисных переменных на основные. В строке x4 находится отрицательный элемент a42=-2, следовательно, столбец x2 - разрешающий. Наименьшее отношение между свободным членом и эл-том разрешающего столбца (см. поле «оценка») будет в первой строке и элемент a32 - разрешающий. Получилась таблица 3 (верхние числа).

Таблица 3

Теперь преобразуем таблицу по следующему алгоритму:

1. Выделим разрешающий элемент aij;

2. Найдём обратную ему величину л=1/aij и запишем её в правом нижнем углу этой же ячейки;

3. Все элементы разрешающей строки, кроме разрешающего элемента, умножим на л и запишем внизу соответствующей ячейки;

4. Все элементы разрешающего столбца , кроме разрешающего элемента, умножим на -л и запишем внизу соответствующей ячейки;

5. Выделим все верхние числа в разрешающей строке, и все нижние - в разрешающем столбце;

6. Для каждого из остальных элементов запишем в нижнюю часть ячейки произведение выделенных чисел, стоящих в той же строке и в том же столбце, что и данный элемент;

7. Перепишем таблицу, заменив переменные: элементы разрешающих строки и столбца - значениями, стоящими в нижних частях этих ячеек; оставшиеся элементы - суммой чисел, стоящих в верхних и нижних частях ячеек.

Применительно к текущему шагу, разрешающий элемент a32, л = 1 / a32 = 1. После указанных выше преобразований, получим новую таблицу (табл. 4):

Таблица 4

Решение снова не может быть опорным, т.к. присутствует отрицательный свободный член во второй строке. Попытаемся ликвидировать его путём замены базисных переменных на основные. Но в строке x4 больше нет отрицательных элементов, следовательно, невозможно выбрать разрешающий столбец. Заметим, что в строке целевой функции нет отрицательных элементов, значит оптимальное решение, в случае отмены ограничений на переменные, достигнуто. Ограничивающая система уравнений не имеет решений при неотрицательных значениях всех переменных.

Ответ:

Система уравнений несовместима в области положительных значений переменных.

Примечание:

Этот же результат получен и при решении данной задачи в пакете Mathematica:

Задача 3

Таблица 5

Решение

Заметим, что общее количество запасов (700+600+200+200+100=1800) меньше количества заявок (300+700+1000=2000), следовательно имеем открытую транспортную задачу с избытком заявок. Добавим строку с фиктивными запасами для дополнения задачи до задачи закрытого типа. После корректировки получаем транспортную задачу с правильным балансом (табл. 6):

Таблица 6

Найдём опорное решение методом наименьших затрат (табл. 7):

Таблица 7

Выбранный план перевозок является допустимым, т.к. при нём все заявки удовлетворены и все запасы израсходованы, сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу - заявке соответствующего пункта назначения. Сумма запасов равна сумме заявок, и выражается числом 2000, стоящим в правом нижнем углу таблицы. Данное распределение является базисным (заполнено m+n-1=8 ячеек таблицы), следовательно, задача готова к решению.

Первоначально затраты на перевозку составят:

Составим матрицу оценок методом потенциалов:

Начнём с первого столбца. Пусть потенциал этого столбца равен нулю. Рядом с потенциалом в скобках записываем номер шага. После прибавления потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (1;1) не изменится; чтобы полученный после сложения коэффициент стал равен 0, потенциал первой строки таблицы должен быть равен -10; для обнуления коэффициента затрат клетки (1;2) потенциал второго столбца должен быть -10 и т.д.

Изменённые коэффициенты выписываются в виде матрицы оценок:

Критерий оптимальности (базисное распределение поставок верно тогда и только тогда, когда оценки всех свободных клеток неотрицательны) на данном шаге не выполнен - присутствуют 2 свободные клетки с отрицательными оценками.

Продолжим оптимизацию (табл. 8). Составим цикл пересчёта для клетки (5;2) и дадим поставку неё:

Таблица 8

В верхнем правом углу знаком «+» отмечаются те клетки, поставки в которые увеличатся, а знаком «-» - те, в которые уменьшатся. Наибольшая возможная поставка, исходя из текущего цикла пересчёта равна min {100, 100, 100} = 100. Передвигаем её по циклу (табл. 9):

Таблица 9

После передвижения освободились сразу 2 клетки, решение перестало быть базисным. Для того, чтобы оно осталось базисным, дадим фиктивную поставку в клетку (4;2).

Снова составляем матрицу оценок по вышеприведённому алгоритму:

На текущем шаге клеток с отрицательной оценкой нет, следовательно, критерий оптимальности выполнен.

Проверим решение с помощью метода потенциалов (табл. 10). Примем a1 = 0, тогда bj = cij - ai (для заполненных клеток). Если найденное решение справедливо, то во всех пустых клетках таблицы Дij = cij - (ai + bj ) ? 0, и Дij = 0 в заполненных клетках. Получим следующую таблицу (в скобках показаны оценки клеток):

Таблица 9

Условие Дij ? 0 выполняется, следовательно, решение верное.

Ответ:

Таблица 10

Суммарные затраты на перевозку составляют:

Задача 4

Условие

1. Кремер Н. Ш., Путко Б. А., Трощин И. М. «Исследование операций в экономике» - М.: ЮНИТИ, 2004. - 407 с.

2. Плотникова Н. В. Курс лекций (ПС)