Практикум по решению линейных задач математического программирования
![]()
2) Определяем
базисные переменные
– это
.
![]()
3)
Заполняем
первую таблицу
| Базис |
|
В | 2 | 3 | 0 | 0 | 0 | 0 |
|
|
|
|
|
|
|
|
||||
|
|
0 | 18 | 1 | 3 | 1 | 0 | 0 | 0 |
|
|
|
0 | 16 | 2 | 1 | 0 | 1 | 0 | 0 |
|
|
|
0 | 5 | 0 | 1 | 0 | 0 | 1 | 0 |
|
|
|
0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | – |
|
|
0 |
–2 |
–3 |
0 |
0 |
0 |
0 |
||
Здесь
и
не удовлетворяют
условию оптимальности,
т. к. они меньше
нуля. Выбираем
среди них большее
по модулю. Это
.
Следовательно,
столбец переменной
– разрешающий.
Значит, в новый
базис нужно
ввести переменную
.
Находим
:
;
;
![]()
Наименьшее
из этих чисел
– это число 5,
что соответствует
строке базисной
переменной
.
Значит, строка
базисной переменной
– разрешающая,
следовательно,
из базиса нужно
вывести переменную
.
Элемент
=1
– разрешающий.
Новый базис:
.
Заполнение
следующей
таблицы начинаем
со столбцов
«Базис» и «
».
Потом заполняем
разрешающую
строку, разделив
каждый ее элемент
на разрешающий,
т.е. на 1. Все элементы
разрешающего
столбца будут
нулями, кроме
разрешающего,
который всегда
равен 1. Столбцы
под
переписываем
без изменения,
т. к. эти переменные
остались в
базисе. Остальные
элементы новой
таблицы находим
по правилу
прямоугольника.
Например, элемент
найдем из
прямоугольника
=
![]()
Или элемент
=
из прямоугольника
Оценки
для новой таблицы
можно находить
по этому же
правилу.
В
целом, решение
данной задачи
симплексным
методом в виде
таблиц будет
иметь вид
| Базис |
|
В | 2 | 3 | 0 | 0 | 0 | 0 |
|
|
|
|
|
|
|
|
||||
|
|
0 | 18 | 1 | 3 | 1 | 0 | 0 | 0 | 6 |
|
|
0 | 16 | 2 | 1 | 0 | 1 | 0 | 0 | 16 |
|
|
0 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | 5 |
|
|
0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | – |
|
|
0 | –2 | –3 | 0 | 0 | 0 | 0 | таб. 1 | |
|
|
0 | 3 | 1 | 0 | 1 | 0 | –3 | 0 | 3 |
|
|
0 | 11 | 2 | 0 | 0 | 1 | –1 | 0 | 5,5 |
|
|
3 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | – |
|
|
0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | 7 |
|
|
15 | –2 | 0 | 0 | 0 | 3 | 0 | таб. 2 | |
| Базис |
|
В | 2 | 3 | 0 | 0 | 0 | 0 |
|
|
|
|
|
|
|
|
||||
|
|
2 | 3 | 1 | 0 | 1 | 0 | –3 | 0 | – |
|
|
0 | 5 | 0 | 0 | –2 | 1 | 5 | 0 | 1 |
|
|
3 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | 5 |
|
|
0 | 12 | 0 | 0 | –3 | 0 | 9 | 1 |
|
|
|
21 | 0 | 0 | 2 | 0 | –3 | 0 | таб. 3 | |
|
|
2 | 6 | 1 | 0 | –0,2 | 0,6 | 0 | 0 | |
|
|
0 | 1 | 0 | 0 | –0,4 | 0,2 | 1 | 0 | |
|
|
3 | 4 | 0 | 1 | 0,4 | –0,2 | 0 | 0 | |
|
|
0 | 3 | 0 | 0 | 0,6 | –1,8 | 0 | 1 | |
|
|
24 | 0 | 0 | 0,8 | 0,6 | 0 | 0 | таб. 4 | |
Оценочная
строка четвертой
таблицы показывает,
что получен
оптимальный
план, так как
все
.
– это значения
из столбца В,
т.е.
,
,
,
.
Свободные
(небазисные)
переменные
.
Итак,
=
(6; 4; 0; 0; 1; 3),
=
=
24.
Примечание:
При переходе
от таблицы к
таблице для
контроля сравнивают
,
которое должно
быть не меньше
предыдущего
для задачи на
максимум и не
больше предыдущего
– для задачи
на минимум.
При использовании симплексного метода возможны следующие случаи.
1) Если в
оценочной
строке симплекс-таблицы
оценка
=
0 соответствует
свободной
переменной,
то это означает,
что ЗЛП имеет
не единственный
оптимальный
план.
2) Если при переходе от одного опорного плана к другому в разрешающем столбце нет положительных элементов, то это означает, что целевая функция ЗЛП является неограниченной и оптимальных планов не существует.
Задания для самостоятельной работы.
Определить оптимальный план задач, используя симплексный метод решения задач линейного программирования:
| а) |
|
б) |
|
Понятие двойственности
1) Симметричные двойственные задачи
Рассмотрим
задачу производственного
планирования.
Пусть предприятие
имеет m
видов ресурсов
объемом
единиц. Эти
ресурсы должны
быть использованы
для выпуска
n видов
продукции.
Пусть
– норма потребления
i-го вида
ресурса на
производство
единицы j-ой
продукции;
– цена реализации
j-ой продукции;
– объем производства
j-ой продукции,
обеспечивающий
предприятию
максимальную
выручку.
План
производства
следует составить
из условия
максимизации
общей стоимости
продукции
при ограничениях
на использовании
ресурсов

,
![]()
Или в краткой форме записи математическая модель задачи имеет вид:
(1)
,
(2)
,
(3)
Задачу (1) – (3) называют исходной.
По исходным данным задачи (1) – (3) сформируем другую экономическую задачу.
Предположим,
что предприятию
разрешено на
его усмотрение
реализовать
все указанные
ресурсы. Необходимо
установить
цены на них –
,
,
пользуясь
следующими
соображениями:
покупатель стремится минимизировать их общую стоимость;
предприятие согласно
