еометрический (графический) метод решения задачи.

птимизационные методы и модели в управлении экономическими системами.

2.1. Линейное программирование.

Принцип оптимальности в планировании и управлении, общая задача оптимального программирования. Формы записи задачи линейного программирования и ее экономическая интерпретация. Геометрическая интерпретация задачи (геометрический метод решения задачи). Симплексный метод решения задач линейного программирования (с естественным и искусственным базисом). Теория двойственности в анализе оптимальных решений экономических задач.

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

ероятностно-статистичесике методы моделирования экономических систем.

Теория массового обслуживания. Классификация систем массового обслуживания. Количественные характеристики. Показатели эффективности систем массового обслуживания.

алансовый метод.

Экономико-математическая модель межотраслевого баланса. Коэффициенты прямых и полных материальных затрат.

Далее в данных методических указаниях представлены варианты контрольной работы и краткие указания по ее выполнению.

Контрольная работа выполняется студентами индивидуально на основе лекционного материала. Номер варианта контрольной работы - это последняя цифра номера зачетной книжки (цифре 0 соответствует 10 вариант).

ЗАДАНИЯ ДЛЯ КОНТРОЛЬНОЙ РАБОТЫ

ВАРИАНТ №1

адача 1.

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

_{, ,}

_{, .}

адача 2.

редприятие располагает 3-мя видами сырья и может выпускать одну и ту же продукцию двумя способами. При этом за 1 час работы первым способом выпускается 20 единиц продукции, а вторым способом - 30 единиц продукции. Количество сырья (кг) того или иного вида, расходуемого за 1 час при различных способах производства, и запасы сырья (кг) приведены в таблице.

Тип сырья	Способ производства	Запас сырья, кг.
1сп.	2сп.
С1
С2
С3

Сформулировать экономико-математическую модель задачи и, используя симплексный метод решения задач линейного программирования, найтитакое время (час) использования первого и второго способов производства, при котором будет выпущено наибольшее количество продукции.

адача 3.

Решить следующую транспортную задачу:

А=(100; 150; 50), В=(75;80;60;85), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

На АЗС имеются 2 колонки для заправки автомобилей. Автомобили подъезжают на АЗС в соответствии с пуассоновским распределением со средней частотой 2 автомобиля за 5 мин. Заправка автомобиля в среднем длится 3 мин, и продолжительность заправки распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что у АЗС не окажется ни одного автомобиля;

б) вероятность того, что обе колонки будут заняты;

в) среднюю длину очереди в ожидании заправки;

г) среднее время ожидания автомобиля в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №2

адача 1.

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

_{, ,}

_{, .}

адача 2.

Фирма "Nokia" заключила контракт с администрацией города на прокладку новых телефонных линий двух видов: кабельных (x₁;[км]) и оптоволоконных (x₂;[км]). По условиям контракта фирме будут предоставлены льготы, если она выполнит условия контракта и охватит при этом своей сетью как можно большее пространство города (x₁+x₂). Необходимо определить в какой пропорции строить эти два вида линий связи.

	Вид телефонной линии	Условия контракта (ограничения)
кабельная	оптоволоконная
Трудовые ресурсы (чел./км)
Кол-во единиц техники (ед./км)
Денежные затраты ($/км)

Сформулировать экономико-математическую модель задачи и решить ее, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(300; 350;150; 200), В=(400;400;200), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В парикмахерской работают 3 мастера. Посетители приходят в парикмахерскую в соответствии с пуассоновским распределением со средней частотой 4 человека в час. Стрижка в среднем длится 0,5 часа, и продолжительность стрижки распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что в парикмахерской не окажется ни одного посетителя;

б) вероятность того, что все мастера будут заняты;

в) среднюю длину очереди в ожидании стрижки;

г) среднее время ожидания посетителя в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №3

адача 1.

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

_{, ,}

_{, .}

адача 2.

При проектировании энергосистемы требуется решить, какой мощности строить гидро- и тепловые станции (x₁ и x₂), обеспечивающие общую (x₁+ x₂) максимальную установленную мощность, при условии, что известен удельный расход имеющихся ресурсов на 1МВт установленной мощности и предел по каждому ресурсу.

Ресурсы	Расход ресурсов на 1МВт мощности	Ограничения по ресурсам
ГЭС	ТЭС
Водные ресурсы, км³
Топливо, тыс.т
Кап. вложения, млн.руб.

адача 3.

Решить следующую транспортную задачу:

А=(20; 30;40; 10), В=(40;40;20), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В мастерской по ремонту телевизоров работают 4 опытных мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 9 телевизоров. Каждый мастер успевает отремонтировать 3 телевизора в день, и продолжительность ремонта распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что все мастера свободны от ремонта телевизоров;

б) вероятность того, что все мастера будут заняты;

в) среднюю длину очереди в ожидании ремонта;

г) среднее время ожидания каждым неисправным телевизором начала ремонта.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №4

адача 1.

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

_{, ,}

_{, .}

адача 2.

Для производства трех видов продукции требуются два вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.	Количество сырья, кг.
П1	П2	П3
С1
С2
Прибыль, руб./ед.прод.

Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2 и П3, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(25; 25; 40), В=(15;15;30;30), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В магазине имеются 2 продавца. Покупатели приходят в магазин в соответствии с пуассоновским распределением со средней частотой 3 человека за 5 мин. Обслуживание одного покупателя в среднем длится 3 мин, и продолжительность обслуживания распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что в магазине не окажется ни одного покупателя;

б) вероятность того, что оба продавца будут заняты;

в) среднюю длину очереди в ожидании обслуживания;

г) среднее время ожидания покупателя в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №5

адача 1.

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

_{, ,}

адача 2.

Изготавливается смесь, в которой, кроме прочего, содержание вещества В1 должно быть не более 0,1 %, вещества В2 не более 16 %. Оба вещества содержаться в трех компонентах К1, К2 и К3. Компоненты добавляются к смеси в любых пропорциях и влияют на ее качество. Содержание веществ В1 и В2 в каждом компоненте, а также показатель качества смеси на 1 г каждого компонента приведены в таблице.

Характеристики	Вид компонента
К1	К2	К3
Содержание В1 в 1грамме компонента, %	0,03	0,01	0,01
Содержание В2 в 1грамме компонента, %
Показатель качества смеси, усл.ед./г.

Необходимо определить оптимальное количество компонентов, чтобы показатель качества смеси был максимален. Сформулировать экономико-математическую модель задачи и решить ее, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(40; 50;30; 70), В=(40;70;80),

где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В обувной мастерской работают 3 мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 10 пар обуви. Каждый мастер успевает отремонтировать 5 пар обуви в день, и продолжительность ремонта распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что все мастера свободны от ремонта обуви;

б) вероятность того, что все мастера будут заняты;

в) среднюю длину очереди в ожидании ремонта;

г) среднее время ожидания каждой парой обуви начала ремонта.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.

Отрасль	Прямые межотраслевые потоки	Конечная продукция

ВАРИАНТ №6

адача 1.

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

_{, ,}

адача 2.

Для выпуска двух видов продукции требуются затраты сырья, рабочего времени и оборудования. Количество ресурсов ограничено. Исходные данные приведены в таблице:

Тип ресурса	Hормы затрат ресурсов на единицу продукции	Наличие ресурсов, т
П1	П2
Сырье, т.
Рабочее время, час.
Оборудование, ед.
Прибыль на единицу продукции, руб.

Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный план выпуска продукции, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(30; 50; 50), В=(20;35;20;55), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

У службы доставки продуктов на дом имеется 2 автомобиля. Заказы на обслуживание поступают в соответствии с пуассоновским распределением со средней частотой 2 заказа в час. Обслуживание каждого заказа в среднем длится 45 мин, и продолжительность обслуживания распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что все автомобили свободны от работы;

б) вероятность того, что оба автомобиля будут заняты;

в) среднюю длину очереди в ожидании обслуживания;

г) среднее время ожидания каждым заказом начала обслуживания.

адача 5.

На основании данных, приведенных в таблице, рассчитать коэффициенты полных материальных затрат и объемы валовой продукции отраслей.

Отрасль	Коэффициенты прямых затрат	Конечная продукция

	0,3	0,4
	0,5	0,1

ВАРИАНТ №7

адача 1.

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

_{, ,}

_{, .}

адача 2.

Для производства двух видов продукции требуются три вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.прод.	Количество сырья, кг.
П1	П2
С1
С2
С3
Прибыль, руб./ед.прод.

Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2, используя симплексный метод решения задач линейного программирования.

адача 3.

Решить следующую транспортную задачу:

А=(50; 35; 45), В=(30;65;25;10), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В часовой мастерской работают 3 мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 3 часов. Каждый мастер успевает отремонтировать 2 часов в день, и продолжительность ремонта распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что все мастера свободны от ремонта;

б) вероятность того, что все мастера будут заняты;

в) среднюю длину очереди в ожидании ремонта;

г) среднее время ожидания каждыми неисправными часами начала ремонта.

адача 5.

Отрасль	Коэффициенты прямых затрат	Конечная продукция

	0,6	0,2
	0,4	0,3

ВАРИАНТ №8

адача 1.

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

_{, ,}

_{, .}

адача 2.

Тип сырья	Расход сырья на единицу продукции, кг/ед.прод.	Количество сырья, кг.
П1	П2
С1
С2
С3
Прибыль, руб./ед.прод.

адача 3.

Решить следующую транспортную задачу:

А=(45; 50; 40), В=(65;35;25;10), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В швейном ателье работают 3 закройщика. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением поступает 5 заказов. Каждый мастер успевает выполнить 2 заказа в течение дня, и продолжительность выполнения заказа распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что все закройщики свободны от работы;

б) вероятность того, что все закройщики будут заняты;

в) среднюю длину очереди в ожидании выполнения заказа;

г) среднее время ожидания каждого заказа в очереди.

адача 5.

Отрасль	Коэффициенты прямых затрат	Конечная продукция

	0,1	0,7
	0,2	0,3

ВАРИАНТ №9

адача 1.

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

_{, ,}

_{, .}

адача 2.

Для производства двух видов продукции требуются два вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.прод.	Количество сырья, кг.
П1	П2
С1
С2
С3
Прибыль, руб./ед.прод.

адача 3.

Решить следующую транспортную задачу:

А=(10; 85; 40), В=(70;35;10;20), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

В супермаркете имеются 4 кассы. Покупатели подходят к кассам в соответствии с пуассоновским распределением со средней частотой 2 человека за 5 мин. Обслуживание одного покупателя в среднем длится 5 мин, и продолжительность обслуживания распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что у касс не окажется ни одного покупателя;

б) вероятность того, что все кассы будут заняты;

в) среднюю длину очереди в ожидании обслуживания;

г) среднее время ожидания покупателя в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать объемы конечной продукции каждой отрасли и коэффициенты полных материальных затрат.

Отрасль	Коэффициенты прямых затрат	Совокупная продукция

	0,5	0,2
	0,3	0,6

ВАРИАНТ №10

адача 1.

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

_{, ,}

_{, .}

адача 2.

Сформулировать экономико-математическую модель задачи, двойственную к исходной. Решить двойственную задачу, используя симплексный метод решения задач линейного программирования.

Исходная задача. Для производства двух видов продукции требуются два вида сырья. Количество сырья ограничено. Необходимо найти оптимальный объем производства продукции П1, П2, чтобы прибыль была максимальной. Исходные данные приведены в таблице:

Тип сырья	Расход сырья на единицу продукции, кг/ед.прод.	Количество сырья, кг.
П1	П2
С1
С2
Прибыль, руб./ед.прод.

адача 3.

Решить следующую транспортную задачу:

А=(20; 40; 70), В=(30;60;15;25), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.

адача 4.

На ж/д вокзале имеются 4 кассы для продажи билетов. Пассажиры подходят к кассам в соответствии с пуассоновским распределением со средней частотой 3 человека за 5 мин. Продажа билетов одному пассажиру в среднем длится 5 мин, и продолжительность ее распределена по экспоненциальному закону. Требуется определить:

а) вероятность того, что у касс не окажется ни одного пассажира;

б) вероятность того, что все кассы будут заняты;

в) среднюю длину очереди в ожидании обслуживания;

г) среднее время ожидания пассажира в очереди.

адача 5.

На основании данных, приведенных в таблице, рассчитать объемы конечной продукции отраслей и коэффициенты полных материальных затрат.

Отрасль	Коэффициенты прямых затрат	Совокупная продукция

	0,2	0,3
	0,1	0,6

КРАТКИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для выполнения контрольной работы

ЗАДАЧА 1.В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции f( ). Общая задача линейного программирования выглядит следующим образом: найти

max(min) f(

)=c₁x₁+c₂x₂+…+ c_nx_n,

(1)

при ограничениях (условиях):

a₁₁x₁+a₁₂x₂+…+ a_1nx_n { }b₁,
a₂₁x₁+a₂₂x₂+…+ a_2nx_n { }b₂,	(2)
………
a_m1x₁+a_m2x₂+…+ a_mnx_n { }b_m,
x_j₀, j =	(3)

где a_i_j, b_i, c_j (i= , j = )— заданные постоянные величины.

Вектор = (х₁, х₂, ..., x_п), удовлетворяющий системе ограничений (2), (3), называется допустимым решением, или планом ЗЛП. План (допустимое решение), который доставляет максимум или минимум целевой функции (1), называется оптимальным планом (решением) ЗЛП.

еометрический (графический) метод решения задачи.

Если в ЗЛП ограничения заданы в виде неравенств с двумя переменными, она может быть решена графически. Задача ЛП в стандартной форме записи при п=2 выглядит следующим образом:

max(min) f(

)=c₁x₁+c₂x₂,

(4)

при ограничениях (условиях):

a₁₁x₁+a₁₂x₂ b₁,
a₂₁x₁+a₂₂x₂ b₂,
………
a_m1x₁+a_m2x₂ b_m,
x₁0, x₂0.

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой a_i1x₁+a_i2x₂=b_i_,, i= . Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х₁= 0, х₂= 0. Полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая представляет собой многоугольник решений (совокупность точек, координаты каждой из которых составляют решение данной системы).

Графический метод решения ЗЛП состоит из следующих этапов.

Этап 1. Сначала на координатной плоскости x₁0 x₂строится допустимая многоугольная область, соответствующая ограничениям, которая является пересечением множества полуплоскостей. Далее строится вектор-градиент линейной (целевой) функции f( ) в какой-нибудь точке , принадлежащей допустимой области:

Этап 2. Строится прямая c₁x₁+c₂x₂=f( ) (линия уровня: целевая функция во всех точках этой прямой равна f( )),перпендикулярная вектору-градиенту. Затем прямаяпередвигается в направлении вектора-градиента в случае максимизации f( ) до тех пор, пока не покинет пределов многоугольной области. Предельная точка области при этом движении и является точкой максимума f( ). В случае минимизации f( ) прямую c₁x₁+c₂x₂=f( ) надо двигать в направлении, противоположном вектору-градиенту.

Этап 3. Для нахождения координат точки максимума (минимума) достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума (минимума). Значение f( ), найденное в получаемой точке, является максимальным (минимальным).

ЗАДАЧА 2.В данной задаче необходимо найти решение с помощью симплексного метода. Симплексный метод - это универсальный метод решения ЗЛП. Суть его заключается в следующем.

Этап 1. Вначале исходная ЗЛП записывается в канонической форме.

Канонической формой записи задачи линейного программирования (КЗЛП) называют задачу вида:

max f( )=

(5)

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

	(6)
, j = .	(7)

Или в матричном виде: max f( )=CX при условиях AX = B, X 0.

Здесь С = (c₁, c₂,…, c_n,) — вектор-строка; А=(а_ij) — матрица размерности т x п, X и B - вектор-столбцы.

Расширенная матрица этой системы будет иметь вид:

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (2) k-ой дополнительной переменной x_n+k 0 со знаком “-“ в случае ограничения типа и знаком “+” в случае ограничения типа .

Дальнейшее решение ведется в в симплекс-таблицах.

№ табл.	Базис	С_б	План В	с₁	с₂	…	с_j	…	с_n	Q
A₁	A₂	…	A_j	…	A_n
0	A₁	с₁	b₁	a₁₁	a₁₂	…	a_1j	…	a_1n
A₂	с₂	b₂	a₂₁	a₂₂	…	a_2j	…	a_2n
…	…	…	…	…	…	…	…	…
A_i	с_i	b_i	a_i1	a_i2	…	a_ij	…	a_in
…	…	…	…	…	…	…	…	…
A_m	с_m	b_m	a_m1	a_m2	…	a_mj	…	a_mn
	L			…	_j	…

Рис.1. Симплексная таблица

Этап 2. Предварительно получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (т.н. начальное опорное решение).

Для этого матрица системы уравнений должна содержать единичную подматрицу размерностью т х т. Предположим, что после выполнения этапа 1 первые т векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: (b₁, b₂, ..., b_m,0, ...,0). Т.е. основные переменные являются свободными и равными нулю, а дополнительные переменные являются базисными и равны правым частям СЛУ.

Этап 3. Полученный вариант проверяется на оптимальность с помощью критерия оптимальности. Признак оптимальности заключается в следующих двух теоремах.

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие

, где , j = , (т.е. - скалярное произведение векторов столбцов С_б и A_j ), то можно получить новый опорный план, для которого значение целевой функции будет больше исходного.

называют оценкой столбца j.

Теорема 2. Если для всех векторов выполняется условие , то полученный план является оптимальным.

Этап 3. Если решение не оптимальное, переходят к следующему опорному решению (плану) на основе применения метода Жордана-Гаусса для системы линейных уравнений; направление перехода от одного опорного решения к другому выбирается на основе критерия оптимальности исходной задачи.

На основании признака оптимальности в базис вводится вектор A_k, давший минимальную отрицательную величину симплекс-разности:

= z_k - c_k = min(z_j- c_j), j = , (т.е. имеющий минимальную отрицательную оценку)

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор А_r, который дает минимальное положительное отношение

Q = , a_ik>0, i= .

Строка A_r называется направляющей, столбец А_k и элемент a_rk — направляющими (или ведущими).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по методу Жордана-Гаусса.

Число L в симплексной таблице – это текущее значение целевой функции: , т.е. скалярное произведение векторов столбцов С_б и В.

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

Для использования приведенной выше процедуры симплекс-метода к минимизации линейной формы f( ) следует искать максимум функции f₁( ) = - f( ), затем полученный максимум взять с противоположным знаком. Это и будет искомый минимум исходной ЗЛП.

С каждой ЗЛП тесно связана другая линейная задача, называемая двойственной, первоначальная задача называется исходной или прямой.

Модель двойственной задачи имеет вид:

g( )= min ,	(8)
,	(9)
, i = .	(10)

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1) целевая функция исходной задачи (5)-(7) формулируется на максимум, а целевая функция двойственной задачи (8)-(10 ) - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид , а в задаче на минимум – вид ;

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений (6) исходной задачи, и аналогичная матрица

в двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений (6) исходной задачи, а число ограничений в системе (9) двойственной задачи - числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции (8) двойственной задачи являются свободные члены в системе (6) ограничений исходной задачи, а правыми частями в ограничениях (9) двойственной задачи - коэффициенты при неизвестных в целевой функции (5) исходной задачи;

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства , соответствует переменная, связанная условием неотрицательности.

ЗАДАЧА 3.

Транспортная задача по критерию стоимости в общем виде формулируется следующим образом. В т пунктах отправления А₁, А_{2, …,}, А_m , которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим a_i ( i = 1, 2, ..., т). Данный продукт потребляется в п пунктах B₁, B_{2, …,}, B_n, которые будем называть потребителями; объем потребления обозначим b_j(j = 1, 2, ..., n). Известны расходы на перевозку единицы продукта из пункта A_i в пункт B_j, которые равны c_ij и приведены в матрице транспортных расходов С = (c_ij).

Требуется составить такой план прикрепления потребителей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов А_i, в пункты B_j в соответствии с потребностью и общая величина транспортных издержек будет минимальной.

Обозначим количество продукта, перевозимого из пункта A_j в пункт B_j, через х_ij. Совокупность всех переменных х_ij для краткости обозначим .

Наиболее применяемым методом решения данной задачи является метод потенциалов, при котором каждой i-й строке (i-му поставщику) устанавливается потенциал u_i, который можно интерпретировать как цену продукта в пункте поставщика, а каждому столбцу j (j-му потребителю) устанавливается потенциал v_j, который можно принять условно за цену продукта в пункте потребителя. В простейшем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т.е.

v_j=u_i+c_ij.

(11)

Следует отметить, что ранг системы линейных уравнений равен т + п - 1; таким образом из общего числа т п неизвестных базисных неизвестных будет т + п - 1. Вследствие этого при любом допустимом базисном распределении в матрице перевозок (таблице поставок), представленной в общем виде на рис. 2, будет занято ровно т + п - 1 клеток, которые будем называть базисными в отличие от остальных свободных клеток; занятые клетки будем отмечать диагональной чертой.

Рис.2. Таблица поставок

Алгоритм метода потенциалов для закрытой транспортной задачи таков.

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

При каждом из этих методов при заполнении некоторой клетки, кроме последней, вычеркивается или только строка матрицы перевозок, или только столбец; лишь при заполнении последней клетки вычеркиваются и строка, и столбец.

В методе северо-западного угла всегда в первую очередь заполняется клетка (из числа невычеркнутых), стоящая в верхнем левом (северо-западном) углу матрицы перевозок. В различных модификациях метода наименьших стоимостей заполнение клеток матрицы перевозок проводится с учетом значений величин c_ij. Так, в модификации «двойного предпочтения» отмечают клетки с наименьшими стоимостями перевозок сначала по каждой строке, а затем по каждому столбцу. Клетки, имеющие две отметки, заполняют в первую очередь, затем заполняют клетки с одной отметкой, а данные о нераспределенном грузе записывают в неотмеченные клетки с наименьшими стоимостями.

Вторым этапом служат построение системы потенциалов на основе равенства (11) и проверка начального плана на оптимальность; в случае его неоптимальности переходят к третьему этапу.

Введем специальные показатели u_i для каждой строки матрицы перевозок (каждого поставщика), где , и показатели v_j для каждого столбца (каждого потребителя), где . Эти показатели называются потенциалами поставщиков и потребителей, их удобно интерпретировать как цены продукта в соответствующих пунктах поставщиков и потребителей. Потенциалы подбираются таким образом, чтобы для заполненной клетки (i;j) выполнялось равенство (11).

Совокупность уравнений вида (11), составленных для всех заполненных клеток (всех базисных неизвестных), образует систему т + п - 1 линейных уравнений с т+п неизвестными u_i и v_j. Эта система всегда совместна, причем значение одного из неизвестных можно задавать произвольно (например, и₁= 0), тогда значения остальных неизвестных находятся из системы однозначно.

Чтобы оценить оптимальность распределения, для всех клеток (i;j) матрицы перевозок определяются их оценки, которые обозначим через d_i_j, по формуле:

d_ij=(u_i+c_ij)- v_j.

(12)

Используя ранее принятую интерпретацию, выражение (u_i+c_ij) можно трактовать как сумму цены продукта у поставщика и стоимости перевозки; эта сумма путем вычитания сравнивается с ценой продукта у соответствующего потребителя v_j. Очевидно, оценки заполненных клеток равны нулю. Таким образом, условием оптимальности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок. Оценки клеток по формуле (12) удобно представить в виде матрицы оценок.

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

Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой; если таких клеток несколько, то обычно выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой. Для выбранной клетки строится замкнутая линия (контур), начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках; при этом направления отдельных отрезков контура могут быть только горизонтальными и вертикальными. Вершиной контура, кроме первой, является занятая клетка, где отрезки контура образуют один прямой угол. Очевидно, число отрезков контура, как и его вершин, будет четным. В вершинах контура расставляются поочередно знаки «+» и «-», начиная со знака «+» в выбранной свободной клетке.

Величина перераспределяемой поставки определяется как наименьшая из величин поставок в вершинах контура со знаком «-», и на эту величину увеличиваются поставки в вершинах со знаком «+» и уменьшаются поставки в вершинах со знаком «-». Это правило гарантирует, что в вершинах контура не появится отрицательных поставок, начальная выбранная клетка окажется занятой, в то время как одна из занятых клеток при этом обязательно освободится.

Пример простого контура показан пунктиром на рис. 3.

Рис. 3. Пример таблицы поставок

ЗАДАЧА 4.

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

В данной задаче рассматривается модель СМО с ожиданием, в которой требования, поступившие в момент, когда все обслуживающие каналы заняты, ставятся в очередь и обслуживаются по мере освобождения каналов.

Общая постановка задачи состоит в следующем. Система имеет п обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование. В систему поступает простейший (пуассоновский) поток требований с параметром . Если в момент поступления очередного требования в системе на обслуживании уже находится не меньше п требований (т.е. все каналы заняты), то это требование становится в очередь и ждет начала обслуживания. Время обслуживания каждого требования t_об— случайная величина, которая подчиняется экспоненциальному закону распределения с параметром . Система является разомкнутой, т.е. поступающий поток требований можно считать неограниченным.