Учебный проект "Решение задач оптимального планирования"
методическая разработка по информатике и икт (11 класс) по теме

Поиск оптимального решения (графическим методом)

ЗАДАНИЕ: 

Колхоз имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика - 4000 руб., пятитонного - 5000 руб.

Колхоз может выделить для приобретения автомашин 141 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?

Задачу решить графическим  методом.

РЕШЕНИЕ: 

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

Ввод переменных:

Пусть x1 – количество трехтонных автомашин,

x2 – количество пятитонных автомашин.

Цель задачи: Максимизация грузоподъемности.

Введем целевую функцию – грузоподъемность автомашин:

f = 3*x1+ 5*x2.

Ограничения:

Возможности колхоза ограничены финансовыми возможностями и количеством машин, которые может приобрести.

На приобретение грузовиков необходима сумма:  

4000*x1+ 5000*x2,

при этом по условию она не должна превосходить 141 000.

Колхоз может приобрести не более определенного количества машин, т.е.,

0 ≤ x1≤ 19,

0 ≤ x2 ≤ 17.

Таким образом, задача заключается в следующем: максимизировать целевую функцию

f = 3*x1+ 5*x2 → max 

при ограничениях

Графическое решение:

Строим многоугольник решений (область допустимых решений задачи). Он ограничен прямыми:

Множество точек, определяемых неравенствами  – многоугольник АВСДО, в одной из вершин которого достигается максимум функции.

Построим линию уровня 3*x1 + 5*x2 =0 и вектор градиента n (3, 5).

Будем передвигать линию уровня, пока не выйдем из многоугольника, что произойдет в точке В с координатами  (14, 17).

В этой точке, где x1=14, x2=17 функция принимает максимальное значение 127.  

Ответ:

Максимальная грузоподъемность 127 т. Чтобы достичь максимального значения грузоподъемности, нужно приобрести 14 трехтонных грузовиков и 17 пятитонных.

A

B

C

D

O