Материал: 1820

Z 20x1 25x2 min

3x1 4x2 18,

5x1 7x2 25,6x1 8x2 32,

x1 0,x2 0.

Задачи

1. Торговое предприятие реализует четыре группы товаров 1,2,3,4. Нормы расходов ресурсов на каждую группу товаров, запасы ресурсов, а также прибыль от единицы каждого вида продукции заданы в таблице

Определить объем продаж товаров, чтобы прибыль торгового предприятия была максимальной.

2.Диетолог разработал диету, состоящую из сливочного масла, мяса, хлеба и фруктов. Содержание калорий, белков, жиров, углеводов и холестерина (в 100 г. продукта), нормы потребления (в сутки) и цена 100 г. соответствующего продукта указаны в таблице

Составить математическую модель задачи.

3. Ресторан обслуживает сотрудников обедами из трех блюд. Затраты на производство, доставку, накладные расходы, товарооборот для каждого блюда, прибыль от реализации каждой партии блюд указаны в таблице

16

Плановый фонд ресурсов имеет следующие значения: затраты на приготовление блюд не должно превышать 900 чел-час., на доставку потребителям – 500 чел.-час., накладные расходы могут быть не более 3000 руб. и план товарооборота равен 8000 руб. Требуется определить, какое количество каждого вида блюд необходимо выпускать, чтобы обеспечить максимальную прибыль ресторана. Составить ЗЛП.

2.2 Практическое занятие №6 (4 часа). Графический метод решения ЗЛП. Цель занятия: научиться решать задачи линейного программирования с двумя

независимыми переменными графическим способом.

Методические указания.

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется при решении задач с двумя независимыми переменными x1 , x2 и когда ограничениями являются неравенства.

Порядок решения задачи линейного программирования:

1. На плоскости в координатных осях x1 , x2 строятся прямые соответствующие исходным ограничениям – неравенствам.

2.Указываются полуплоскости, удовлетворяющие каждому из ограничений.

3.Определяется многоугольник решений, указывая координаты вершин на нем, который называется областью допустимых решений (ОДР). Вычисляются значений целевой функции во всех вершинах многоугольника решений. Выбирая наибольшее и наименьшее значение из этих вычисленных величин, определяются экстремальные значения целевой функции.

4.Экстремальные значения можно определить, построив линию уровня, полагая F =0 или принимая значение целевой функции F = const.

которого показывает возрастание целевой функции и является перпендикуляром к линиям уровня. Перемещая линию уровня в направлении gradF до вершины ОДР (точки касания), можно найти максимальное значение целевой функции. Перемещая линию уровня в направлении противоположном gradF до вершины ОДР (точки касания), можно найти минимальное значение целевой функции.

17

максимум линейной функции равен Fmax 2 6 3 4 24.

Рис. 1

Задачи

Решить геометрически задачи линейного программирования:

2.3. Практическое занятие №7 (4 часа). Симплексный метод (аналитический метод) решения ЗЛП

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

Методические указания.

В основу симплексного метода легла идея последовательного улучшения решения ЗЛП. Для его реализации необходимо освоить три основные элемента:

-способ определения какого-либо первоначального допустимого базисного решения

задачи;

-правило перехода к лучшему, или не к худшему, решению;

18

- критерий проверки оптимальности найденного решения.

Для использования симплексного метода ЗЛП должна быть приведена к каноническому

виду.

Критерий оптимальности решения при определении максимума (минимума) линейной функции: если в выражении линейной функции через неосновные переменные отсутствуют положительные (отрицательные) коэффициенты при неосновных переменных, то решение оптимально.

Основы этого метода рассмотрим на примере из предыдущего параграфа.

Пример.

Решить симплексным методом задачу:

F 2x1 3x2 max

x1 3x2 18,

2x1 x2 16,

3x1 21,

x2 5

x1 0,x2 0.

Решение:

Введем дополнительные переменные x3 ,x4 , x5 ,x6 , чтобы записать ЗЛП в каноническом

виде:

x1 3x2 x3 18,

2x1 x2 x4 16,

3x1 x5 21,

x2 x6 5.

Определим основные переменные (оп) по следующему правилу: в качестве основных переменных на 1-ом шаге можно взять такие m переменных, каждая из которых входит только в одно из m уравнений системы ограничений, при этом нет таких уравнений системы, в которые не входит ни одна из этих переменных. Если выбранные по этому правилу переменные имеют те же знаки, что и соответствующие им свободные члены в правых частях уравнений, то полученное таким образом базисное решение будет допустимым. Если по этому правилу невозможно определить основные переменные, то нужно действовать стандартно (метод Жордана-Гаусса)

Шаг 1.

Оп: x3 , x4 ,x5 , x6 .

Неосновные переменные (нп): x1 , x2 .

Выражаем оп через нп:

x3 18 x1 3x2,

x4 16 2x1 x2,x5 5 x2,

x6 21 3x1 .

При x1 =0 и x2 =0 получаем базисное решение X1 0,0,18,16,5,21 , которое является допустимым и соответствует вершине О(0,0) многоугольника (рис.1). Так как оно допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через нп: F 2x1 3x2 . При решении X1 значение функции будет равно F X1 =0. Функцию можно увеличить за счет одной из нп, входящих в выражение функции с положительным

19

коэффициентом. В нашем примере будем брать нп, с наибольшим коэффициентом. Таким образом, в оп переведем x2 , а разрешающим будет третье уравнение последней системы.

Переменная x5 переходит в нп.

Шаг 2.

Оп: x2 , x3 ,x4 , x6 . Нп: x1 , x5 .

Выразим новые оп через нп, начиная с разрешающего уравнения:

x2 5 x5,

x3 18 x1 3 5 x5 ,x4 16 2x1 5 x5 ,x6 21 3x1.

И после преобразований

x2 5 x5,

x3 3 x1 3x5,x4 11 2x1 x5,

x6 21 3x1.

Оп: x1 , x2 ,x4 , x6 . Нп: x3 , x5 .

Выразим новые оп через нп, начиная с разрешающего уравнения:

x1 3 x3 3x5

x2 5 x5,

x4 5 2x3 5x5,x6 12 3x3 9x5.

уравнение является разрешающим, переменная x4 переходит в нп.

Шаг 4

Оп: x1 , x2 ,x5 , x6 . Нп: x3 , x4 .

После преобразований получим:

20