Введение актуальность темы

3. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL
линейный программирование симплексный графический
Пример 1: Требуется составить такой рацион кормления животных тремя видами корма, при котором они получат необходимое количество питательных веществ A и B и себестоимость кормов будет минимальна.

Цены кормов, требуемое количество питательных веществ и их содержание в каждом корме показаны в таблице.

Питательные вещества	Корм 1	Корм 2	Корм 3	Требуемое колличество
А	10	6	12	50
Б	7	10	11	45
Цена корма	2,20	1,95	2,87

Если обозначить X=(x1, x2, x3) - искомое количество кормов, то задача ЛП формулируется так:Найти решение X системы:

при котором целевая функция принимает минимальное значение.

Математическую формулировку задачи необходимо оформить в виде таблицы, отражающей основные зависимости.

Внешний вид условия в программе Excel.

Ячейки таблицы имеют следующий смысл:
диапазон A1:C2 - содержит матрицу A;
диапазон D1:D2 - содержит вектор ресурсов В;
диапазон A6:C6 - содержит вектор цен С;
диапазон A4:C4 - содержит вектор решений X, начальные значения которого заданы нулю и который будет оптимизирован программой;
диапазон E1:E2 - содержит выражения, вычисляющие произведение AX;
ячейка E6 - содержит выражение, вычисляющее f=CX.
Вызов программы поиска решения выполняется через меню "Сервис\Поиск решения...". В открывшемся окне "Поиск решения" необходимо установить следующие параметры:
"Установить целевую ячейку" - E6;
установить переключатель "Равной минимальному значению";
в поле "изменяя ячейки" указать диапазон A4:C4;
в области "Ограничения" нажать кнопку "Добавить" и в окне "Добавление ограничений" ввести ограничения: E1>=D1 и E2>=D2;

Окно для ввода исходных данных задачи ЛП в программе Excel

нажать кнопку "Параметры..." и в открывшемся окне установить флажки "Линейная модель", "Неотрицательные значения" и выбрать переключатель "Оценка" - "Линейная".

Окно для ввода параметров решения задачи ЛП

Для запуска программы необходимо в окне "Поиск решения" нажать кнопку "Выполнить". Результаты вычислений будут записаны в изменяемые ячейки таблицы. В итоге таблица должна иметь следующий вид.

Внешний вид условия и полученного решения в программе Excel

Таким образом, животных следует кормить:
первым кормом в количестве 0,38 кг,
третьим - 3,85 кг,
второй корм - не использовать вообще.
При таком рационе затраты на кормление одного животного составят 11,88 руб.
Пример 2+ 2X2 ≥ 14+ 3X2 ≥ 15
X1 + X2 ≥ 10, X2 ≥ 0
X1 + 7 X2 → min
Пример 3
X1 + 14X2 + 15 X3 + 10X4 → max+ X2 + X3 + 2X4 ≤ 3+ 2X2 + 3X3 + X4 ≤ 7, X2, X3, X4 ≥ 0

Графический метод.

Пример 1
Найдем наибольшее значение линейной функции графическим методом.
=x1-x2
при следующих ограничениях:
Решение
В первую очередь, найдем область допустимых значений, т.е. точки x₁ и x₂ , которые удовлетворяют системе ограничений. По условию задачи x₁ 0, x₂ 0 ,т.е. мы рассматриваем только те точки, которые принадлежат первой четверти.
Шаг 1.
Рассмотрим неравенство 1 системы ограничений.
₁ + x₂ 3 _.

· Построим прямую. Заменим знак неравенства на знак равенства .

₁ + x₂ = 3

Преобразуем уравнение следующим образом .

Каждый член уравнения разделим на 3 .

Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую.

На оси X₁ рисуем точку с координатой 3 . На оси X₂ рисуем точку с координатой 3. Соединяем полученные точки и получаем необходимую прямую. Какие точки нас интересуют?

x1+x2≥3≥-x1+3

Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой.

· Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа. Область допустимых значений выделена штриховкой. Точки принадлежащие области допустимых значений:
(3,0)
В(0,3)

Шаг 2.
Рассмотрим неравенство 2 системы ограничений.

₁ + x₂ 7

· Построим прямую. Заменим знак неравенства на знак равенства .

₁ + x₂ = 7

Преобразуем уравнение следующим образом .

Каждый член уравнения разделим на 7 .

Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси X₁ рисуем точку с координатой 7 . На оси X₂ рисуем точку с координатой 7 . Соединяем полученные точки и получаем необходимую прямую.

· Какие точки нас интересуют?
+x2≤7≤-x1+7

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

· Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный ниже. Область допустимых значений выделена штриховкой. Точки принадлежащие области допустимых значений:
A(3,0)(7,0)(0,3)(0,7)

Шаг 2
Рассмотрим неравенство 2 системы ограничений.

+x2≤7

Построим прямую. Заменим знак неравенства на знак равенства .

+x2=7

Преобразуем уравнение следующим образом:

Каждый член уравнения разделим на 7

Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси X₁ рисуем точку с координатой 7 . На оси X₂ рисуем точку с координатой 7 . Соединяем полученные точки и получаем необходимую прямую.

· Какие точки нас интересуют?
+x2≤7≤ -x1+7

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа. Область допустимых значений выделена штриховкой. Точки принадлежащие области допустимых значений:(3 , 0)(7 , 0)(0 , 3)
D(0 , 7)

Шаг 3
Рассмотрим неравенство 3 системы ограничений.₂ 2

Построим прямую. Заменим знак неравенства на знак равенства .₂ = 2

Прямая проходит параллельно оси X₁.
· Какие точки нас интересуют?₂ 2
Знак неравенства больше или равно нуля, следовательно, нас интересуют точки лежащие выше построенной нами прямой.
Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа. Область допустимых значений выделена штриховкой. Точки принадлежащие области допустимых значений:(0 , 3)(0 , 7)(1 , 2)(1 , 2)

Шаг 4
Рассмотрим неравенство 4 системы ограничений.₂ 5

· Построим прямую. Заменим знак неравенства на знак равенства .₂ = 5
Прямая проходит параллельно оси X₁.
· Какие точки нас интересуют?₂ 5
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой
· Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа. Область допустимых значений выделена штриховкой. Точки принадлежащие области допустимых значений:(0 , 3)(0 , 5)(1 , 2)(5 , 2)(2 , 5)

Шаг 5
Рассмотрим неравенство 5 системы ограничений.₁ 4

· Построим прямую. Заменим знак неравенства на знак равенства .₁ = 4
Прямая проходит параллельно оси X₂.
· Какие точки нас интересуют?₁ 4
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие левее построенной нами прямой.
· Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа. Область допустимых значений выделена штриховкой. Точки принадлежащие области допустимых значений:(0 , 3)(0 , 5)(1 , 2)(2 , 5)(4 , 3)(4 , 2)

Шаг 6
Вернемся к нашей исходной функции L .= x₁ - x₂

Допустим значение функции L равно 1 (абсолютно произвольно выбранное число), тогда

= x₁ - x₂

Данное уравнение является уравнением прямой на плоскости. Из курса аналитической геометрии известно, что данная прямая перпендикулярна вектору , координатами которого являются коэффициенты функции, а именно вектору

Следовательно, с геометрической точки зрения, наша исходная функция L изображается как множество прямых перпендикулярных вектору

Построим вектор _. На рисунке правее, вектор изображен красным цветом.Вектор нарисован не в масштабе,исключительно для большей наглядности.

Причем очевидно, что значение функции будет возрастать при перемещении прямой в направлении вектора _. Диапазон перемещения прямой НЕ от точки O до точки N, а именно, в направлении от точки O к точке N. Будем перемещать прямую, перпендикулярную вектору ,до тех пор, пока она полностью не пройдет область допустимых решений. В нашем случае, касание прямой, перед выходом из области допустимых решений, произойдет в точке N (4 , 2). В данной точке значение функции будет наибольшим.

Ответ : Наибольшее значение функция достигает при x₁ = 4, x₂ = 2.

Значение функции : L = 2.