Общая постановка задачи линейного программирования

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

В разделе 1 мы упоминали об оптимизационных моделях. К одним из наиболее изученных классов таких моделей относятся математические модели линейного программирования. Становление этого класса задач относится к 50-м годам прошлого века и связано с решением практических задач в экономике.

1. Задача оптимального использования ресурсов.

Фирма планирует начать выпуск шкафов и столов для компьютеров. Исходные данные приведены в следующей таблице стандартного вида.

Ресурсы	Запасы	Расх. коэфф.
шкафы столы
Дсп, м^2		3,5 1
Стекло, м^2		1 2
Труд, чел-часы		1 1
Прибыль, у.е.		200 100

Менеджеру фирмы требуется составить оптимальный план выпуска изделий из условия максимальной прибыли.

Построение математической модели (следуем п. 1.1):

Пусть х₁ – количество шкафов, х₂- количество столов

По условию,

3,5 х₁ + х₂ ≤ 350

х₁ + 2х₂ ≤ 240

х₁ + х₂ ≤ 150 → ограничения модели

х₁, х₂ ≥ 0

F = 200x₁ + 100x₂ → max (целевая функция)

Смысл модели: найти такой набор переменных х₁, х₂, который удовлетворяет ограничениям и при этом обращает целевую функцию в максимум.

2. Задача о раскрое

Имеются прутки длиной 100 см. Требуется нарезать из них заготовки длиной 25 см. (200 штук), 30 см. (250), 35 см. (150). Возможные варианты раскроя приведены в таблице:

Вар. раскроя										План
Вид заготовки
Обрезь

Требуется определить, сколько прутков нужно разрезать по каждому варианту (х₁,х₂,…х₉), чтобы выполнить план по заготовкам и при этом минимизировать суммарную обрезь.

Построение математической модели:

4х₁ + х₄ + х₅+ 2х₆ + 2х₇ + х₉ = 200

3х₂ + х₃ + х₅+ х₆ + 2х₈ + 2х₉ = 250

2х₃ + 2х₄ + х₅+ х₆ + х₇ + х₈ = 150

х_i ≥ 0

F= 10х₂ + 5х₄ +10 х₅+ 20х₆ + 15х₇ +5 х₈+15x₉ →min

3. Транспортная задача.

На двух железнодорожных станциях сосредоточено топливо для трех электростанций. Исходные данные приведены в таблице:

Потребители				Запасы, тонн
Поставщики
Спрос, тонн

В клетках указаны затраты на перевозку одной тонны от поставщиков к потребителям.

Требуется составить оптимальный план перевозок топлива от поставщиков к потребителям, чтобы

а) вывезти все топливо

б) удовлетворить спрос

в) минимизировать суммарные затраты

Построение математической модели:

Положим х_{i j} – количество груза, перевозимого от i-го исходного пункта к j-му пункту назначения.

х₁₁ + х₁₂ + х₁₃ =300

х₂₁ + х₂₂ + х₂₃ =500

х₁₁ + х₂₁ =500

х₁₂ + х₂₂ =200

х₁₃ + х₂₃ =100

х_ij ≥ 0

F = 7х₁₁ + 9х₁₂ + 8х₁₃ + 3х₂₁ + 4х₂₂ + 6х₂₃ → min

1. Задача линейного программирования в каноническом виде

а₁₁х₁ + а₁₂х₂+……а_1nх_n = в₁

а₂₁х₁ + а₂₂х₂+……а_2nх_n = в₂ (1)

……………………………

а_m1х₁ + а_m2х₂+……а_mnх_n = в_m

x_i ≥ 0, i = 1,n

F = c₁х₁ + c₂х₂+……c_nх_n → max

Матричная запись:

Ах = в

х ≥ 0

F = c x → max

Здесь А – матрица коэффициентов, х – столбец переменных,

в- столбец правых частей, с - строка коэффициентов целевой функции.

Какие возможны ситуации?

1) Система (1) не имеет решений. Интерес такая ситуация не представляет.

2) Система (1) имеет единственное решение. Ясно, что оно и будет оптимальным решением.

3) Система (1) имеет бесконечное множество решений, но целевая функция не ограничена на множестве допустимых решений. Экономически такой случай не интересен. Он лишь свидетельствует о недостатке построения модели.

4) Система (1) имеет бесконечное множество решений, и целевая функция ограничена на множестве допустимых решений. Именно такой случай экономически представляет наибольший интерес. Рассмотрим его более подробно.

Теоретические основы линейного программирования. (без доказательства).

Дата добавления: 2014-12-27