Задачи линейного программирования
Краткая теория
Линейное программирование — область математики, разрабатывающая
теорию и численные методы решения задач нахождения экстремума (максимума или
минимума) линейной функции многих переменных при наличии линейных ограничений,
т. е. равенств или неравенств, связывающих эти переменные.
Методы линейного программирования применяют к практическим задачам,
в которых:
- необходимо выбрать наилучшее решение (оптимальный план) из
множества возможных;
- решение можно выразить как набор значений некоторых переменных
величин;
- ограничения, накладываемые на допустимые решения специфическими
условиями задачи, формулируются в виде линейных уравнений или неравенств;
- цель выражается в форме линейной функции основных переменных.
Значения целевой функции, позволяя сопоставлять различные решения, служат
критерием качества решения.
Для практического решения экономической задачи математическими
методами ее прежде всего следует записать с помощью математических выражений:
уравнений, неравенств и тому подобное, то есть составить
экономико-математическую модель. Исходя из отмеченных выше особенностей задач
линейного программирования, можно наметить следующую общую схему формирования
модели:
- выбор некоторого числа переменных величин, заданием числовых
значений которых однозначно определяется одно из возможных состояний
исследуемого явления;
- выражение взаимосвязей, присущих исследуемому явлению, в виде
математических соотношений (уравнений, неравенств); эти соотношения образуют
систему ограничений задачи;
- количественное выражение выбранного критерия оптимальности в
форме целевой функции;
- математическая формулировка задачи как задачи отыскания
экстремума целевой функции при условии выполнения ограничений, накладываемых на
переменные.
Модель задачи линейного программирования может быть записана в
одной из приведенных ниже форм:
1. Общая или произвольная
форма записи задачи линейного программирования:

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

– произвольные

2. Симметричная или стандартная форма записи
задачи линейного программирования:
3. Каноническая или основная
форма записи задачи линейного программирования:



Указанные выше три формы записи ЗЛП эквивалентны в том смысле, что
каждая из них с помощью несложных преобразований может быть сведена к другой
форме, то есть если имеется способ нахождения оптимального решения задачи в
одной из указанных форм, то тем самым может быть определен оптимальный план
задачи в любой другой форме (говорят о стратегической эквивалентности задачи в
любой из форм).
Так, при необходимости задачу минимизации можно заменить задачей
максимизации, и наоборот.

Неравенство типа
путем умножения левых и правых частей на -1
можно превратить в неравенство типа
и наоборот. Ограничения-неравенства

преобразуются в ограничения-равенства путем прибавления (вычитания)
к левым частям дополнительных (балансовых) неотрицательных переменных
:

В случае необходимости ограничение-равенство

можно записать в виде системы неравенств:

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

Способы решения задач линейного программирования подробно рассмотрены на соседних страницах сайта:
Примеры решения задач
Задача 1
Имеются
корма двух видов и силос. Их можно использовать для кормления скота в
количестве не более 50 и 80 кг соответственно. Стоимость 1 кг сена -12 ден.ед.,
а силоса -8 ден.ед. Составить кормовой рацион минимальной стоимости. Данные
приведены в таблице:
Питательные
вещества
|
Корма
|
Минимальное
содержание питательных веществ
|
Сено
|
Силос
|
Кормовые ед., кг
|
0,5
|
0,3
|
30
|
Протеин, г
|
40
|
10
|
1000
|
Кальций, г
|
1,25
|
2,5
|
100
|
Фосфор, г
|
2
|
1
|
80
|
Решение
Через
и
обозначим количество сена и силоса
соответственно. Тогда целевая функция, выражающая стоимость рациона:

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

Кроме
того, по смыслу задачи:

Получаем
следующую задачу линейного программирования:



Задача 2
Построить
экономико-математическую модель задачи и найти оптимальный план раскроя с точки
зрения минимизации отходов.
Куски
искусственной кожи по 60 дм разрезать на части по 20 дм, 25 дм и 30 дм так,
чтобы частей по 20 дм было не менее 6 штук, частей по 25 дм было не менее 10
штук и частей по 30 дм было не менее 4 штук.
На сайте можно заказать решение контрольной или самостоятельной работы, домашнего задания, отдельных задач. Для этого вам нужно только связаться со мной:
ВКонтакте
WhatsApp
Telegram
Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту СберБанка. Опыт работы более 25 лет.
Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.
Решение
Способы раскроя
|
Количество
заготовок 1-го вида (20 дм)
|
Количество заготовок 2-го вида (25 дм)
|
Количество заготовок 3-го вида (30 дм)
|
Количество отходов
|
I
|
3
|
-----
|
----
|
|
II
|
----
|
2
|
----
|
|
III
|
---
|
----
|
2
|
|
IV
|
---
|
1
|
1
|
|
V
|
1
|
----
|
1
|
|
VI
|
1
|
1
|
----
|
|
План
|
6
|
10
|
4
|
|
Обозначим через
искомые величины количества заготовок из
кожи, раскраиваемых соответствующим
образом.
Тогда целевая функция экономико-математической
модели:
Экономико-математическая модель имеет следующие ограничения:

Кроме
того, по смыслу задачи:

Задача 3
Составить
экономико-математическую модель задачи линейного программирования.
Найти
оптимальное сочетание посевов трех культур: пшеницы, гречихи и картофеля.
Эффективность возделывания названных культур (в расчете на 1 га) характеризуется
показателями, значения которых приведены в таблице. Производственные ресурсы:
6000 га пашни, 5000 чел.-дней труда механизаторов, 9000 чел.-дней ручного
труда. Критерий оптимальности – максимум прибыли.
Показатель
|
Пшеница
|
Гречиха
|
Картофель
|
Урожайность, ц
|
20
|
10
|
100
|
Затраты
механизаторов, чел.-дней
|
0.5
|
1
|
5
|
Затраты ручного
труда, чел.дней
|
0.5
|
0.5
|
20
|
Прибыль от
реализации 1 ц продукции, ден.ед.
|
4
|
10
|
3
|
Решение
Через
и
обозначим количество собираемой пшеницы,
гречихи и картофеля соответственно.
Тогда
ограничение на количество пашни:

Ограничение
на затраты труда механизаторов:

Ограничения
на затраты ручного труда:

Кроме
того, по смыслу задачи:

Целевая
функция, выражающая получаемую от реализации прибыль:

Получаем
следующую экономико-математическую модель:


