Лабораторная работа № 3.
Тема: Специальные задачи линейного программирования и их решение средствами Excel. К рассматриваемым в пособии задачам относятся задачи целочисленного программирования, экономические задачи, сводимые к транспортной задаче, задача о ранце, задача о закреплении парка самолетов за воздушными линиями и некоторые другие.
Программное обеспечение: Microsoft Excel
Основные сведения
1. Целочисленные задачи линейного программирования.
К задачам целочисленного программирования относятся экстремальные задачи, переменные которых по смыслу задачи могут принимать только целочисленные значения.
Рассмотрим конкретную задачу целочисленного программирования.
Задача.
В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено S кв.м площади. На приобретение оборудования предприятие может израсходовать A руб. при этом оно может купить оборудование n видов. Единица оборудования i-го вида стоит ai руб. Приобретение оборудования i-го вида позволяет увеличить выпуск продукции в смену на bi ед. Для установки одного оборудования i-го вида требуется ci кв.м. площади. Определить сколько единиц оборудования каждого вида необходимо закупить, чтобы максимально увеличить выпуск продукции.
Построение математической модели. Предположим, что предприятие закупит оборудование i-го вида в количестве xi шт.
Целевая функция задачи описывает увеличение объема выпуска продукции, которое должно быть максимальным, т.е.
F = b1 x1 + b2 x2 + … + bn xn → max.
Запишем теперь ограничения задачи.
Первое ограничение относится к стоимости оборудования и выделенной для этой цели денежных средств:
a1 x1 + a2 x2 + … + an xn ≤ A.
Второе ограничение относится к размеру площади, которое может быть выделено под оборудование:
c1 x1 + c2 x2 + … + cn xn ≤ S .
По смыслу задачи, количество оборудования может быть только целым и неотрицательным числом:
xi ≥ 0 и xi – целые
2. Задачи сводящиеся к транспортной модели
Довольно обширный класс экономических задач, не имеющих ничего общего с транспортной задачей, тем не менее сводится к транспортной модели, и для решения таких задач может быть использован алгоритмы и методы решения транспортных задач (Методическое пособие Лабораторная работа №2. Транспортные задачи и их решение средствами Excel).
В этом случае величины транспортных тарифов имеют различный смысл в зависимости от конкретной экономической задачи, как и величины поставляемых грузов от поставщиков и потребности в них у потребителей.
Рассмотрим конкретную задачу.
Задача. Имеется n участков земли, на которых могут быть засеяны m видов культур. Площадь каждого участка соответственно равна si. Каждой i-ой культурой следует засеять площадь vi . Урожайность каждой из культур для каждого из участков различна и задается матрицей C= {cij}.
Определить, сколько гектаров каждой культуры на каждом из участков следует засеять так, чтобы общий сбор зерна был максимальным.
Построение математической модели
Обозначим искомые величины – площадь культуры j засеянной на участке i , как xij , i = 1, …, n, j =1, …, m.
Целевая функция представляет собой суммарную урожайность всех культур со всех участков. Так как урожайность культуры j с единицы площади участка i равна сij , то урожайность этой культуры с площади xij составит сij xij . Суммарная урожайность – целевая функция, которая должна принимать максимальное значение
.
Ограничения задачи. Поскольку на каждом из трех участков засеиваются все четыре культуры, то сумма площадей занимаемой каждой культурой на каждом участке, должна быть равна имеющейся площади этого участка:
, i = 1, …, n
С другой стороны, суммарная площадь отводимая под каждую культуру, которая засеивается на каждом участке, также должна быть равна заданной площади
, j =1, …, m
Площади культур не могут выражаться отрицательными величинами и потому необходимо выполнение условий:
xij ≥ 0, i = 1, …, n, j =1, …, m
Эта модель по ограничениям полностью совпадает с математической моделью транспортной задачи. Модель является сбалансированной.
В данной задаче необходимо максимизировать целевую функцию. Для перехода к стандартной транспортной модели надо заменить функцию F на противоположную функцию F' = – F, которую необходимо минимизировать, т.е.
Далее задача решается известными методами.