2020-10-11
201
Решить задачу ЦЛП.
Решаем задачу ЛП симплекс-методом. Оптимальная таблица имеет вид
| b | 
| 
| |
| L | -14/3 | -4/3 | -2/3 |
| 5/3 | 1/3 | 2/3 |
| 4/3 | 2/3 | -2/3 |
Оптимальное решение 
не является целочисленным. Выберем среди нецелочисленных переменных 
переменную с максимальной дробной частью и построим соответствующее отсечение:
Приписывая это ограничение к симплексной таблице и проводя стандартное преобразование двойственным симплекс-методом, получим:
| b |
| 
| |
| L | -14/3 | -4/3 | -2/3 |
| 5/3 | 1/3 | 2/3 |
|
| 4/3 | 2/3 | -2/3 |
| -2/3 | -1/3 | -2/3 |
| b |
|
| |
| L | -4 | -1 | -1 |
|
| 1 | 0 | 1 |
|
| 2 | 1 | -1 |
|
| 1 | 1/2 | -3/2 |
Полученная таблица является оптимальной. Соответствующее оптимальное решение 
является целочисленным. Значение функции на этом решении 
.
Пример построения опорного плана методом
северо-западного угла
|
| 1 | 2 | 3 |
| ||||||||
| 1 | 15 | 20 | 35 | 20 | 0 | 0 | ||||||
| 2 |
| 0 | 30 | 30 | 30 | 30 | ||||||
|
| 15 | 20 | 30 | = | ||||||||
| 0 | 20 | 30 | ||||||||||
| 0 | 0 | 30 | ||||||||||
| 0 | 0 | 0 | ||||||||||
|
|
|
В таблице, обведенной снизу и справа двойной чертой, указаны объемы перевозок, полученные методом северо-западного угла. При этом небазисные нулевые перевозки не проставлены. Справа и внизу таблицы содержатся объемы возможных запасов и спросов. В число базисных перевозок вошла перевозка 
, так как на предыдущем шаге 
и по п.3 метода считается выбывшим только поставщик, а неудовлетворенный спрос второго потребителя равен 
.
Пример построения опорного плана методом
минимальной стоимости
|
| 1 | 2 | 3 |
| |||||||||
| 1 | 9 | 57 | 301 | 35 | 5 | 5 | 5 | ||||||
| 2 | 152 | 153 | 8 | 30 | 30 | 15 | 0 | ||||||
|
| 15 | 20 | 30 | = | |||||||||
| 15 | 20 | 0 | |||||||||||
| 0 | 20 | 0 | |||||||||||
| 0 | 5 | 0 | |||||||||||
