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

В строке f все коэффициенты неотрицательны кроме коэффициента при искусственной переменной y7, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, симплекс-методом получено оптимальное решение: Y = (3, 0, 0, 4, 0, 0, 0)T, X = (3, 0, 0), f = 3 + 5*0 + 2*0 = 3.

. Решение задачи двойственной к исходной

Приведем систему неравенств и целевую функцию к следующему виду:

Составим следующие векторы и матрицу коэффициентов:

c = (-1, -5, -2) -коэффициенты целевой функции;

b = (-2, -3) - свободные коэффициенты;

A = - коэффициенты из приведенной системы неравенств.

Сформулируем двойственную к исходной задачу на основе полученных коэффициентов. Свободные коэффициенты станут коэффициентами новой целевой функции, коэффициенты целевой функции станут новыми свободными коэффициентами, а коэффициенты системы неравенств образуют новую систему неравенств следующего вида:

;

Запишем задачу в канонической форме для возможности применить симплекс-метод, для этого введем три переменные w3, w4, w5:

= (0, 0, 1, 2, 5)T

Данная система является системой с базисом, следовательно, для решения можно применить симплекс-метод. Запишем начальную симплекс-таблицу: