Решение задач линейной оптимизации симплекс – методом
Составим таблицу, отвечающую первой итерации.
В столбце Бх, в пятой позиции базиса место
вектора А9 занимает вектор А1. Соответствующий ему
коэффициент линейной формы С41 = 0 помещаем в столбец Сх.
Главная часть таблицы 1 заполняется по данным таблицы 0 в соответствии с
рекуррентными формулами. Так как все
, то опорный план
является решением L-задачи. Наибольшее значение линейной формы равно
.
Таблица 3.2.1

3.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи
Поскольку
, где
- оптимальный опорный план L-задачи, то
является начальным опорным планом исходной задачи (2.12) - (2.13).
4. Решение исходной задачи I алгоритмом симплекс-метода
Описание I алгоритма
Симплекс-метод позволяет, отправляясь от некоторого исходного опорного плана и постепенно улучшая его, получить через конечное число итераций оптимальный план или убедиться в неразрешимости задачи. Каждой итерации соответствует переход от одной таблицы алгоритма к следующей. Таблица, отвечающая опорному плану в ν-й итерации имеет вид табл. 4.1.
Таблица 4.1
| C |
|
… |
|
… |
|
… |
|
||||
| N |
|
|
B |
|
… |
|
… |
|
… |
|
t |
| 1 |
|
|
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| l |
|
|
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| m |
|
|
|
|
… |
|
… |
|
… |
|
|
| m+1 | – | – |
|
|
… |
|
… |
|
… |
|
– |
Заполнение таблицы, соответствующей исходному опорному
плану (0-й итерации). Пусть
некоторый опорный план
задачи (2.1) - (2.3) с базисом
. Тогда
– базисные компоненты,
а
– небазисные
компоненты.
Вычисляем коэффициенты разложения векторов